@article{moizumi:agent-plan,
    author = {Katsuhiro Moizumi and George Cybenko},
    title = {The Traveling Agent Problem},
    journal = {Mathematics of Control, Signals and Systems},
    year = {2001},
    volume = {14},
    number = {3},
    pages = {213--232},
    publisher = {Springer-Verlag},
    copyright = {Springer-Verlag},
    group = {agents, actcomm, coabs},
    url = {http://agent.cs.dartmouth.edu/papers/moizumi:agent-plan.ps.gz},
    abstract = {This paper considers a sequencing problem which arises naturally
in the scheduling of software agents. We are given n sites at which a certain
task might be successfully performed. The probability of success is $p_i$ at
the $i$th site and these probabilities are independent. Visiting site i and
trying the task there requires time (or some other cost metric) $t_i$ whether
successful or not. Latencies between sites $i$ and $j$ are $l_{ij}$, that is,
the travel time between those two sites. Should the task be successfully
completed at a site then any remaining sites do not need to be visited. The
{\em Travelling Agent Problem} is to find the sequence which minimizes the
expected time to complete the task. The general formulation of this problem
is NP-Complete. However, if the latencies are constant we show that the
problem can be solved in polynomial time by sorting the ratios $p_i/t_i$
according to decreasing value and visiting the sites in that order. This
result then leads to an efficient algorithm when groups of sites form subnets
in which latencies within a subnet are constant but can vary across subnets.
We also study the case when there are deadlines for solving the problem in
which case the goal is to maximize probability of success subject to
satisfying the deadlines. Applications to mobile and intelligent agents are
described.}
}