Mobile agent planning problems.
Katsuhiro Moizumi · 1999
Mobile agents have received much attention recently as a way toe ciently access distributed resources in a low bandwidth network. Planning allows mobile agents to make the best use of the available resources. This thesis studies several planning problems that arise in mobile agent information retrieval and data-mining applications. The general description of the planning problems is as follows: We are given sites at which a certain task might be successfully performed. Each site has an independent probability of success associated with it. Visiting a site and trying the task there requires time (or some other cost matrix) regardless of whether the task is completed successfully or not. Latencies between sites, that is, the travel time between those two sites also have to be taken into account. If the task is successfully completed at a site then the remaining sites need not be visited. The planning problems involve nding the best sequence of sites to be visited, which minimizes the expected time to complete the task. We name the problems Traveling Agent Problems due to their analogy with the Traveling Salesman Problem. This Traveling Agent Problem is NPcomplete in the general formulation. However, in this thesis a polynomial-time algorithm has been