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

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 . and the running time is limited by a polynomial on problem size and 1/ #2;.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.