JUCS - Journal of Universal Computer Science 16(3): 372-401, doi: 10.3217/jucs-016-03-0372
Mobile Agent Routing with Time Constraints: A Resource Constrained Longest-Path Approach
expand article infoEduardo Camponogara, Ricardo Boveto Shima
‡ Federal University of Santa Catarina, Florianópolis, Brazil
Open Access
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.
mobile agents, constrained routing, constrained longest-path, dynamic programming, approximation algorithms