@phdthesis{moizumi:thesis,
    author = {Katsuhiro Moizumi},
    title = {The mobile-agent planning problem},
    year = {1998},
    school = {Thayer School of Engineering, Dartmouth College},
    copyright = {Katsuhiro Moizumi},
    group = {agents, actcomm, coabs},
    url = {http://agent.cs.dartmouth.edu/papers/moizumi:thesis.ps.gz},
    keyword = {mobile agent, planning, traveling salesperson, network sensing,
routing},
    abstract = {Mobile agents have received much attention recently as a way to
efficiently 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 finding the best sequence of
sites to be visited, which minimizes the expected time to complete the task.
We name the problems {\em Traveling Agent Problems} due to their analogy with
the Traveling Salesman Problem. This Traveling Agent Problem is $NP$-complete
in the general formulation. However, in this thesis a polynomial-time
algorithm has been successfully developed to solve the problem by adding a
realistic assumption to it. The assumption enforces the fact that the network
consists of subnetworks where latencies between machines in the same
subnetwork are constant while latencies between machines located in different
subnetworks vary. Different versions of the Traveling Agent Problem are
considered: (1) single agent problems, (2) multiple agent problems (multiple
agents cooperate to complete the same task) and (3) deadline problems (single
or multiple agents need to complete a task without violating a deadline
constraint at each location in the network). Polynomial and pseudo-polynomial
algorithms for these problems have been developed in this thesis. In addition
to the theory and algorithm development for the various Traveling Agent
Problems, a planning system that uses these algorithms was implemented.
Descriptions of the mobile agent planning system with its supporting
components such as network sensing system, directory service system, and
clustering system, are also given in this thesis.}
}