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/.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.