Mobile Agent Routing with Time Constraints: A Resource Constrained Longest-Path Approach

Eduardo Camponogara (Federal University of Santa Catarina, Brazil)

Ricardo Boveto Shima (Federal University of Santa Catarina, Brazil)

Abstract: Mobile agent technology advocates the mobility of code rather than the transfer of data. As data is found in several sites, a mobile agent has to plan an itinerary to visit several sites where it collects resources to accomplish its mission. This gives rise to the mobile-agent itinerary problem (MIP) which seeks a route maximizing overall benefit from the resources while meeting a deadline. This paper formalizes MIP and develops a reduction to the resource constrained longest-path problem (CLPP) in acyclic graphs. A dynamic programming (DP) algorithm was designed to produce a family of optimal routes, allowing a mobile agent to dynamically revise its route. A fully-polynomial approximation scheme was developed to reduce the pseudo-polynomial running time of DP, whereby the distance to the optimal is controlled by a parameter ffl and the running time is limited by a polynomial on problem size and 1/ffl. The paper reports results from experiments assessing the performance of the algorithms and discusses extensions to handle non-additive objectives, non-additive constraints, and probabilistic resource constraints.

Keywords: approximation algorithms, constrained longest-path, constrained routing, dynamic programming, mobile agents

Categories: F.2.2, G.2.2, I.2.11