Full text of DOI:10.1007/PL00009883

Math. Control Signals Systems ꢀ2001) 14: 213±232
ꢀ 2001 Springer-Verlag London Limited
Mathematics of Control,
Signals, and Systems
The Traveling Agent Problem*
Katsuhiro Moizumiy and George Cybenkoy
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 pi at the ith site
and these probabilities are independent. Visiting site i and trying the task there
requires time ꢀor some other cost metric) ti whether successful or not. Latencies
between sites i and j are lij, 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 Traveling Agent Problem is to ®nd 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 ti=pi according to
increasing value and visiting the sites in that order. This result then leads to an
e½cient 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.
Key words. Stochastic control, Mobile agents, Intelligent agents, Planning,
Dynamic programming.
1. Introduction
Suppose you are shopping for a speci®c item known to be sold in n ‡ 1 stores, si
where 0 U i U n. The probability that store i has the item is known and given by
pi. Moreover, it takes a known time ti to navigate through store i to the section
where the item is stocked thereby determining whether the item is available or
not. Going from store i to store j requires travel time lij. Starting and ending at
store s0, with 0 ˆ t0 ˆ p0, what is the minimal expected time to ®nd the item or
conclude that it is not available?
As this shopping analogy suggests, once the item is found, you are done and
can return to s0 by the most expedient route which may or may not be taking the
*Date received: February 10, 1998. Date revised: November 16, 1999. This work was partially
supported by Air Force O½ce of Scienti®c Research Grants F49620-97-1-0382, F49620-95-1-0305 and
DARPA Contract F30602-98-2-0107.
y
Thayer School of Engineering, Dartmouth College, Hanover, New Hampshire 03755, U.S.A.
fkatsuhiro.moizumi,gvcg@dartmouth.edu.
213

214
K. Moizumi and G. Cybenko
direct path requiring li0 travel time if the item was found at si. With probability
Q
Q
n
n
iˆ1ꢀ1 À pi† ˆ iˆ0ꢀ1 À pi† all sites must be visited. Moreover, once a store is
visited and found not to have the item in stock, there is no reason to go back to
that store. Probabilities for success at di¨erent sites are assumed independent. Site
s0 is the start and end of the shopping task and can be considered ``home.'' Since
0 ˆ p0 ˆ t0, s0 only contributes to the problem through latencies.
This problem arises when planning the actions of mobile software ``agents''
[G], [JvRS], [M2], [W]. Mobile agents are programs which autonomously move
within a computer network from machine to machine typically in an e¨ort to
satisfy an information retrieval and processing requirement. Using the shopping
metaphor from above, the ``stores'' are information servers such as databases
or web servers. The probabilities of success, pi, can be thought of as estimated
from relevance scores given by search engines such as Altavista, Infoseek, and
others. Compute times, ti, and latencies, lij, are obtained from network status
monitors.
In this framework, an agent has a speci®c information request to satisfy, such
as ®nding a topographical map of a given region. The search engine or directory
service identi®es locations, si for i ˆ 1; . . . ; n, together with probabilities ꢀrele-
vance scores), pi, for ®nding the required data at the corresponding sites.
The agent then queries the network status monitor to ®nd latencies and esti-
mated compute times, lij and ti, for those sites. Based on this information, an au-
tonomous agent must plan its itinerary to minimize expected time for successfully
completing the task. Such a mobile agent system has been developed by the
authors and their colleagues at Dartmouth [G], [RGK] and is known as Agent
Tcl. See http://www.cs.dartmouth.edu/@agent/. ꢀActual implementations and
performance results for the algorithms and schedules described in this paper
can be found in [M2].) In addition to this mobile agent application, there are
numerous other planning and scheduling problems which can be formulated in
these terms [P].
Some work on agent planning follows heuristic methods developed by the arti-
®cial intelligence community [AIS], [CT], [DB], [FN], [DF], [M1]. Our work is
devoted to ®nding optimal solutions to speci®c planning problems using e½cient
algorithms from combinatorial optimization, operations research, and stochastic
control [B1], [B3], [CGM], [H].
Formally, we state the problem as:
The Traveling Agent Problem. There are n ‡ 1 sites, si with 0 U i U n. Each site
has a known probability, 0 U pi U 1, of being able to complete the agent's task
successfully and a time, ti > 0, required for the agent to attempt the task at si
regardless of whether the attempt is successful or not. These probabilities are
independent of each other. Travel times or latencies for the agent to move
between sites are also known and given by lij V 0 for moving between site i and
site j. When the agent's task has been successfully completed at some site, the
agent must return to site 0 from which it started. For site 0, p0 ˆ t0 ˆ 0. The
Traveling Agent Problem is to minimize the expected time to complete the task
successfully.

The Traveling Agent Problem
215
Several comments are appropriate.
.
The latencies, lij, can be assumed to be the minimum travel time between
nodes i and j as would typically be used in network routing. This observation
avoids the situation where an indirect path between nodes, without ``stop-
ping'' at the sites along the indirect path, might be shorter than the direct
path.
.
The probabilities, pi, can be thought of as conditioned on attempting the task
at site i. That is
pi ˆ Probꢀsuccess at site i j site i not visited yet†:
Accordingly,
Probꢀsuccess at site i j site i has been visited† ˆ 0 or 1:
This formally handles the site revisiting issue.
.
.
This problem can be formulated as a Markov Decision Problem or discrete
stochastic control problem [B3], [H] in which the state space consists of vec-
tors indexed by sites with coordinate values indicating whether a site has been
visited already or not. Standard dynamic programming algorithms could be
used on this formulation but since the state space is exponentially large in the
number of sites, this formulation is not scalable. However, we will see that in
certain cases the state space can be simpli®ed leading to e½cient dynamic
programming solutions.
If all sites must be visited ꢀso that pi is irrelevant), then the problem reduces
to the classical Traveling Salesman Problem ꢀTSP) which is known to be NP-
Complete.
Section 2 contains the main body of technical results, namely e½cient algo-
rithms for restricted instances of the problem. Extensions of results from Section 3
to the so-called multiple subnetwork case using dynamic programming are given.
Section 3 deals with deadlines while Section 4 is the conclusion and summary.
2. The Traveling Agent Problem
The formal de®nition of the Traveling Agent Problem has been described in the
previous section. A solution to the problem consists of specifying the order in
which to visit the sites, namely a permutation hi1; i2; . . . ; ini of 1 through n. Such
a permutation will be called a tour in keeping with tradition for such problems.
The expected time to complete the task or visit all sites in failure for a tour
T ˆ hi1; i2; . . . ; ini is
ꢀ
!)
jˆkÀ1ꢀ1 À pi †
ꢀli
kÀ1ik
‡ ti ‡ p li 0†
n
X
Y
CT ˆ l0i ‡ ti ‡ p li 0
‡
1
1
i1
1
k
ik
k
j
kˆ2
jˆ1
n
Y
‡
ꢀ1 À pj†ln0:
ꢀ1†
jˆ1

216
K. Moizumi and G. Cybenko
This formula can be understood as follows. The ®rst site, si , on the tour is always
visited and requires travel time l0i to reach. Upon arrival, time ti must be spent
1
1
1
there regardless of success or failure. With probability pi the task is successfully
completed in which case the agent can return to site 0 with time cost li 0. How-
1
1
ever, with probability ꢀ1 À p † there was failure and the agent proceeds to site i2.
i1
The expected value of the contribution involving moving from site i1 to site i2 and
succeeding there is
ꢀ1 À p †ꢀli i ‡ ti ‡ p li 0†:
i1
1
2
2
i2
2
Note that ꢀ1 À p † is the probability of failing at site i2. The third term comes
i2
from failing at sites i1 and i2 so has probability ꢀ1 À p †ꢀ1 À p † which is multi-
i1
i2
plied by the expected time for success at site i3. The general term then has the
form
ꢀprobability of failure at the first k À 1 sites†
 ꢀexpected time for success at site ik†:
Finally, the last term arises when failure occurs at all nodes and we must return to
the originating site. We have used independence of the various probabilities here.
Not surprisingly, this problem is NP-complete [K] as will be shown below. As
observed above, by setting all pi ˆ 0, the problem reduces to a version of the
TSP. However, for all pi ˆ 1 the problem can be solved trivially. The question
then remains, what is the complexity for cases where 0 < pi < 1? We believe this
will cover the majority of practical cases. It is shown below that the problem re-
mains NP-Complete for the case 0 < pi < 1 by a reduction to the Hamiltonian
Circuit Problem.
Note that in the proof, the question is altered so that we are asking whether
there is a tour whose cost, as above, is smaller than or equal to some total length
B. This can be used in a binary search method to ®nd the minimum. Also, input
data should technically be presented in binary, not real, form. The reduction be-
low holds for rational 0 < pi < 1 of any value so this is not a di½culty.
Theorem 1. The Traveling Agent Problem ꢀTAP) is NP-Complete.
Proof. We start by showing that TAP belongs to NP. Given a tour, T, we can
verify if the total expected length CT is smaller than or equal to B by merely using
the formula. This veri®cation can clearly be performed in polynomial time ꢀOꢀn2†
steps speci®cally). Thus, TAP belongs to NP.
Next, we show that the problem is NP-Hard, by proving that the Hamiltonian
Cycle Problem [GJ] can be reduced to TAP. A Hamiltonian cycle in graph G ˆ
hV; Ei is a simple circuit that includes all the vertices V. Thus, a cycle is
expressed as an ordering of the vertices hv1; v2; . . . ; vki such that fvi; vi‡1g A E for
1 U i U k and fvk; v1g A E.
De®ne a TAP with probabilities strictly between 0 and 1 and
ꢁ
0
1
if i; j A E;
if i; j B E;
lij ‡ tj ˆ

The Traveling Agent Problem
217
so that tj ˆ 0 for any vertex on an edge in E and lij ˆ 0 for any edge in E. This
formation can be done in polynomial time.
The graph G has a Hamiltonian cycle if and only if the corresponding TAP
has a tour with expected cost of 0. To see this, assume that the graph G has
a Hamiltonian cycle H. The corresponding tour T in the TAP will have cost 0
because all the time costs for T are 0. On the other hand, if the tour T has cost
0, the latencies and site times must all be 0 along this tour by construction. Here
we use the fact that the probabilities are strictly between 0 and 1 so that the only
way for the cost to be 0 is for the times to be 0 along the tour. Thus graph G has
a Hamiltonian cycle since all the edges in the tour T have to belong to E by
construction again.
9
2.1. Constant Latencies
The complexity of the problem can be reduced when latencies between nodes are
equal. For example, if the processing time at each node is extremely large ꢀcom-
pared with the latency between the nodes), di¨erences among the latencies could
be ignored, or even taken to be zero. Alternately, if no information about inter-
nodal latencies are known, we might assume all of them to be constant. The con-
stant latency assumption is reasonable in the case of a single subnetwork as well.
Accordingly, the assumption that we employ in this section is:
Assumption 1. Latencies between nodes are all the same.
Under this assumption, it turns out that the TAP can be solved in polynomial
time, as we will see below.
Theorem 2. Assume in the TAP that l ˆ lij V 0 for all i; j, namely Assumption 1.
Compute times, ti, can be arbitrary and ti V 0. Probabilities, pi, can be arbitrary
and 0 U pi U 1. Then the optimal tour for the TAP is attained by:
.
.
First, dropping sites with pi ˆ 0.
Secondly, sorting the ratios for the remaining sites,
ti ‡ l
;
pi
into increasing order and visiting the sites in that order.
Proof. Clearly, any site for which pi ˆ 0 should not be visited at all, that is, it
should be dropped from any prospective tour.
For the remaining sites, the proof uses an interchange argument commonly
used in ®nance and economics. See [B2] for example. We step through the argu-
ment so that the treatment here is self-contained.

218
K. Moizumi and G. Cybenko
For notational convenience and without loss of generality consider the speci®c
tour T ˆ h1; 2; 3; . . . ; ni for the remaining sites. The total expected cost for the
tour T is as in ꢀ1) with notational changes:
ꢀ
!)
n
n
kÀ1ꢀ1 À pj†
ꢀlkÀ1k ‡ tk ‡ pklk0† ‡ ꢀ1 À pj†ln0
X
X
Y
Y
CT ˆ l01 ‡ t1 ‡ p1l10
‡
kˆ2
jˆ1
jˆ1
ꢀ
!)
n
n
kÀ1ꢀ1 À pj†
ꢀl ‡ tk ‡ pkl† ‡ ꢀ1 À pj†l
Y
Y
ˆ l ‡ t1 ‡ p1l ‡
kˆ2
jˆ1
jˆ1
ꢀ
)
kÀ1ꢀ1 À p † ꢀtk ‡ l†;
n
X Y
ˆ 2l ‡ t1 ‡
j
kˆ2 jˆ1
where we have used the fact that
k
pk Á l Á kÀ1ꢀ1 À pj† ‡ l Á ꢀ1 À pj† ˆ l Á kÀ1ꢀ1 À pj†:
Y
Y
Y
jˆ1
jˆ1
jˆ1
This also eliminates the last term so note that pn does not explicitly arise in the
®nal expression because regardless of the value of pn, we return to s0 after visit-
ing sn.
Now consider the e¨ect of switching the order of two adjacent sites on the tour,
say i and i ‡ 1 for some 1 U i U n À 1. Call this new tour T 0.
In the above expression for the expected cost, only the ith and ꢀi ‡ 1†st terms
are a¨ected by the switch. The terms appearing before the ith term do not contain
anything which involves i or i ‡ 1. On the other hand, terms that follow the
ꢀi ‡ 1†st term all contain ꢀ1 À pi† Á ꢀ1 À pi‡1† in precisely the same way but no
other ingredients that depend on either i or i ‡ 1. Note that for i ‡ 1 ˆ n there are
no terms following the two terms we are isolating so we can handle that case as
well by the following argument.
The di¨erence in expected cost between T and T 0 can be calculated by compar-
ing only these two terms. The di¨erence in the expected cost is therefore:
i
CT À CT ˆ ꢀti ‡ l† iÀ1ꢀ1 À p † ‡ ꢀti‡1 ‡ l† ꢀ1 À pj†
Y
Y
0
j
jˆ1
jˆ1
À ꢀti‡1 ‡ l† iÀ1ꢀ1 À p † À ꢀti ‡ l†ꢀ1 À p
†
iÀ1ꢀ1 À pj†
Y
Y
j
i‡1
jˆ1
jˆ1
ˆ ꢀti ‡ l ‡ ꢀti‡1 ‡ l†ꢀ1 À p † À ti‡1 À l À ꢀti ‡ l†ꢀ1 À p †† iÀ1ꢀ1 À pj†
Y
i
i‡1
jˆ1
ˆ ꢀpi‡1ꢀti ‡ l† À p ꢀti‡1 ‡ l†† iÀ1ꢀ1 À pj†:
Y
i
jˆ1

The Traveling Agent Problem
219
Thus, T is a better tour ꢀhas smaller expected cost) if
pi‡1ꢀti ‡ l† < piꢀti‡1 ‡ l†
or, equivalently,
ti ‡ l ti‡1 ‡ l
<
:
pi
pi‡1
This shows that when two adjacent sites have the above ratios out of order ꢀthat
is the ith site on the tour has a larger ratio than the ꢀi ‡ 1†st site), then we can
decrease the expected cost by switching them.
So we can for example perform a Bubble Sort on any initial tour ordering and
every swap in the Bubble Sort will decrease the expected time for the tour. The
optimal value is then the sequence with increasing ratios as above.
9
An important observation is the fact that ti ‡ l is the expected time to reach site
i and process there after failing at site i À 1. We would obtain the same results if
we used the expected time after site i but before reaching sites i ‡ 1 or the home
sites, s0. That expected time is
ti ‡ ꢀ1 À pi†l ‡ pil;
which is equal to ti ‡ l and does not change the result of above.
In fact, the expected time, ti ‡ l, can be replaced by any expected time which is
invariant with respect to the position of the site within the tour. This will be of key
importance in the next section.
This observation and a small construction allows us to solve the following
modi®ed problem.
Theorem 3. Suppose the latency from the home site, s0, to all the other sites is a
constant, l0 0 l, where l is the latency between sites i and j for 1 U i; j U n. Then the
optimal tour is still obtained by:
.
.
Dropping sites with pi ˆ 0.
Sorting the sites into increasing order of
ti ‡ l
:
pi
Proof. Create a new site, sÃ, whose latency to all sites si for i > 0 is l and whose
latency to site s0 is l0 À l ꢀthis might be negative but it does not a¨ect the argu-
ment). Consider any tour, T, using this site, sÃ, as the home. Call the cost of the
tour using sà as home, DT . Let the cost of the tour for the original problem be
CT .
Then the relationship between the costs of the tours is
DT ˆ CT À 2ꢀl0 À l†
because any tour must start and end at either s0 or sÃ, even if l0 À l < 0. Because
of this relationship between costs, the minimal expected time tour for the two

220
K. Moizumi and G. Cybenko
problems are the same. The best tour using sà can be computed using Theorem 1
and by the above is the best tour for this modi®ed problem as well.
9
We use a simple technical lemma based on the proof of Theorem 1. For this
lemma, suppose that we have a general TAP with arbitrary latencies. This means
that the expected time to visit site si, where expected time is measured from the
time an agent arrives at si until it either successfully ®nishes or travels to the next
site. If site si is followed by site sj, then that time is
ti ‡ pili0 ‡ ꢀ1 À pi†lij:
In general, this time depends on both i and j but the lemma below addresses the
case when a subinterval of a tour ꢀa set of consecutive sites of a tour) can be re-
arranged without a¨ecting these expected times. Accordingly, in the lemma we
e
write ti ˆ ti ‡ pili0 ‡ ꢀ1 À pi†lij as the expected time at site si when it is indepen-
dent of j.
Theorem 4. Suppose that we have a general TAP with a tour, T ˆ hs1; s2; s3;
. . . ; sni. Suppose that for a subinterval of the tour, hsi; . . . ; sji for i < j, any per-
e
mutation of the sites si; . . . ; sj results in the same expected execution times, tk, for
each of those sites, then the optimal ordering for the subinterval ꢀthat is, the per-
mutation of the subinterval that minimizes expected time) is obtained by the permu-
tation hsk ; sk ; . . . ; sk i in which
i
i‡1
j
f
t
f
t
g
t
kj
ki
ki‡1
U
U Á Á Á U
:
pk
pk
pk
i
i‡1
j
Proof. As in the proof of Theorem 2, consider switching two adjacent sites, say
sk ; sk , in any ordering of the subinterval in question. Call the original tour T
m
m‡1
and the tour with switched sites T 0. Since the expected times for these sites are
independent of their ordering in the subinterval, we as above see that
f
g
0
CT À CT ˆ Pꢀpk tk À p tk † U 0
km
m
m‡1
m‡1
if and only if
g
f
t
t
km‡1
km
V
;
pk
pk
m‡1
m
where P > 0 is the probability that failure has occurred at all the sites preced-
ing sk . Thus this sorted order minimizes the expected time for the subinterval
m
of sites.
9
2.2. The Multiple Subnetwork Case
Assumption 1 and Theorem 2 address the case of completely constant latencies.
Theorem 3 o¨ers a small generalization in which latencies to the home node can
be di¨erent but still constant. However, many situations can be modeled by vari-
able latencies which are constant within subnetworks and across subnetworks.
Speci®cally, consider the case of two subnetworks ꢀone in Japan and one in the

The Traveling Agent Problem
221
US). Latencies between any two nodes within the same subnetwork are constant
as are latencies across the two subnetworks. That is, for sites in Japan, latencies
are a constant, lJ, and in the USA they are lU. Latencies between two nodes, one
in Japan and one in the USA, are a third constant, lJU. Formally, we de®ne the
Two Subnetwork Traveling Agent Problem ꢀTSTAP) as follows.
Assumption 2. The relevant sites belong to two subnetworks, S1 and S2. Each sub-
network i has a gateway gi. Sites in Si are sij where 1 U j U ni and they are not
the gateways. There are three latencies: L1; L2; L12 V 0. For s1j; s1k A S1, we have
l1j1k ˆ l1k1j ˆ L1. Similarly, for s2j; s2k A S2, we have l2j2k ˆ l2k2j ˆ L2. L12 is the
latency between the gateways g1 and g2. For s1j A S1; s2k A S2, l1j2k ˆ l2k1j ˆ L1 ‡
L12 ‡ L2 ˆ L102. Probabilities pmj > 0 are nonzero and independent as before.
Compute times tmj V 0 are arbitrary but nonnegative. Latencies between the home
site, s0, and sites in Si are L0i ‡ Li ˆ L00i where L0i is the latency between the
home site and the gateway gi. We assume that L0i is the shortest route between
the home site and the gateway i. Thus, L01 U L02 ‡ L21 and L02 U L01 ‡ L12.
Assumption 2A. The relevant sites belong to two subnetworks, S1 and S2. Sites in
Si are sij where 1 U j U ni. There are three latencies: L1; L2; L12 V 0. For s1j A S1,
s2k A S2, l1j2k ˆ l2k1j ˆ L12 while for s1j; s1k A S1, we have l1j1k ˆ l1k1j ˆ L1. Sim-
ilarly, for s2j; s2k A S2, we have l2j2k ˆ l2k2j ˆ L2. Probabilities pmj > 0 are nonzero
and independent as before. Compute times tmj V 0 are arbitrary but nonnegative.
Latencies between the home site, s0, and sites in Si are L0i. We have L01 ˆ L02. We
assume that L0i; L12 V Li. That is, latencies within a subnetwork are smaller than
latencies across networks and to the home sites.
Under Assumption 2, we assume that there is a gateway at each subnetwork and
that the gateway must be visited by an agent when entering or leaving a sub-
network ꢀin the traditional sense of a network gateway). Under Assumption 2A,
we do not assume the existence of such a gateway. However, the latency from the
home site and each subnetwork is assumed to be equal, that is L01 ˆ L02. Under
either assumption, the TSTAP can be solved in polynomial time using the results
of Theorem 3 and dynamic programming. The result can be generalized in several
ways but we defer that discussion until after the basic case is handled. Formally,
we will show:
Theorem 5. Under Assumption 2 or Assumption 2A, the optimal ꢀminimal ex-
pected time) sequence for the TSTAP can be computed in polynomial time,
Oꢀn1 log n1 ‡ n2 log n2 ‡ ꢀn1 ‡ 1†ꢀn2 ‡ 1††.
Outline of the Proof. The proof consists of two steps. The major di¨erence
between this problem and the previous cases of all constant latencies is that now
the optimal solution requires making choices about whether to stay in the same
subnetwork or to cross over to the other subnet after each site is visited.
We ®rst show that the order in which sites are visited in one of the subnets
is given by the ordering speci®ed by Theorems 2 and 3. This greatly reduces

222
K. Moizumi and G. Cybenko
the number of choices necessaryÐafter visiting a site, we only need to decide
which of the eligible sites, one per subnetwork at most, should be visited next. The
sorting requires Oꢀn1 log n1 ‡ n2 log n2† steps.
This sorted ordering is used in the second step where a dynamic programming
algorithm is used to compute the optimal solution. Even though the problem is
stochastic, it can be solved by a deterministic dynamic programming algorithm in
roughly Oꢀꢀn1 ‡ 1†ꢀn2 ‡ 1†† steps.
We only prove the Assumption 2 case. The proof under Assumption 2A is
similar and details are left to the reader.
Proof. As before, eliminate all sites with pij ˆ 0 since they contribute time but
no possibility of solution.
Assertion 1. Suppose that the optimal tour is
hsi j ; si j ; . . . ; si i;
M jM
1
1
2 2
where M ˆ n1n2. Without loss of generality, let the sites in Si be visited in this
order:
si1; si2; si3; . . . ; sin :
i
Then
tiꢀ jÀ1† ‡ piꢀ jÀ1†Li00 ‡ ꢀ1 À piꢀ jÀ1††Li
tiꢀ j† ‡ piꢀ j†Li00 ‡ ꢀ1 À piꢀ j††Li
U
piꢀ jÀ1†
piꢀ j†
for 1 U j À 1 U ni À 1.
We show the result for subnetwork 1 and then see that it applies by symmetry
to subnetwork 2 as well.
First, note that if a tour consists of consecutive visits to sites within S1, then
those sites within S1 must be ordered according to the claim of the theorem by the
interchange argument of Theorems 2 and 3. That is, switching any two adjacent
sites, s1j and s1ꢀ j‡1†, within S1 ꢀwithout a intervening trip to S2) leads to a di¨er-
ence in the expected time that is precisely of the form seen before. This means that
the ordering has to follow
g
f
t1ꢀ j‡1†
p1ꢀ j‡1†
t1j
U
:
p1j
Notice that the last site within S1 before crossing over to a site in S2 has a latency
ꢀin the case of failure) of L102 ˆ L1 ‡ L12 ‡ L2 which in general di¨ers from L1.
However, in the expression for the expected completion time that latency is mul-
tiplied by the probability of failure at all preceding sites so that term is invariant
under the ordering of the preceding sites. That last site in S1 must therefore follow
the above prescribed ordering as well. ꢀAnother way to see this, with details left
to the reader, is to introduce an arti®cial site after the last site visited in S1 and
before crossing over to S2. Making the latency from S1 to this arti®cial site L1 and
the latency from the arti®cial site to S2 the remaining latency, it can be seen that
the above holds as well.)

The Traveling Agent Problem
223
The only remaining case is when two sites within S1 are separated on a tour by
a visit to some sites within S2. This case establishes the claim of the theorem by
using aggregated sites and works only for the optimal tour, not any valid tour.
We will point out where optimality of the tour is used.
De®ne metasites to be aggregated sites within subnetwork 2 that are visited
between visits to subnetwork 1. Using the above notation, suppose that between
visiting s1j and s1ꢀ j‡1† we visit only sites within subnetwork 2, say s2k; . . . ; s2m. We
treat the subnetwork 2 sites s2k; . . . ; s2m as if they were a single site.
The expected time from starting at s1j and arriving at s2k is technically
t1j ‡ p1jL100 ‡ ꢀ1 À p1j†L102 and the probability of success is p1j. However, we de-
®ne a modi®ed site, s1Ãj with
t1Ãj ˆ t1j ‡ p1jL100 ‡ ꢀ1 À p1j†L1;
as the new expected time and probability of success p1Ãj ˆ p1j as before.
For the metasite ms2k:2m, de®ne the expected time to be
t
ˆ L102 À L1 ‡ t2k ‡ p2kL200 ‡ ꢀ1 À p2k†L2
ms2k:2m
‡ ꢀ1 À p2k†ꢀt2ꢀk‡1† ‡ p2ꢀk‡1†L200 ‡ ꢀ1 À p2ꢀk‡1††L2
‡ Á Á Á ‡ ꢀ1 À p2m†L102 ‡ L2†† Á Á Á††:
The probability of success for this metasite is
p
ˆ p2k ‡ ꢀ1 À p2k†p2ꢀk‡1† ‡ ꢀ1 À p2k†ꢀ1 À p2ꢀk‡1††p2ꢀk‡2†
ms2k:2m
‡ Á Á Á ‡ mÀ1ꢀ1 À p2i†p2m
:
Y
iˆk
This time is merely the expected time to start at s2k and either ®0nish successfully
or travel and start at site s1ꢀ j‡1† together with the di¨erence L12 À L1 which is
leftover from the s1j to s2k travel time that is not accounted for in t1Ãj.
By splitting the expected time for site s1Ãj and the metasite ms2k:2m in this way,
we see that the expected time to complete visiting s1Ãj and ms2k:2m is independent of
whether another S1 node follows s1Ãj or such a metasite follows s1Ãj. Similarly, the
time for ms2k:2m is independent of which S1 site precedes it.
To reiterate, we have rede®ned the expected time for s1j so that it is as if the
next site were an S1 site instead of ms2k:2m. Moreover, the excess latency we
removed from s1j has been added to the time for ms2k:2m
.
This means that as long as either another S1 site follows s1Ãj or ms2k:2m follows
s1Ãj, the expected time for s1Ãj is constant. Similarly, as long as the site preceding
ms2k:2m has a latency of L1 to reach the site following it ꢀthat is, it is an S1 site),
the expected time for ms2k:2m is constant.
For notational simplicity, we use the following names:
Ã
.
The site preceding s1j in S1 is called a where an agent makes a decision
whether it should stay in S À 1 or move to another subnetwork.
Sites s1j; ms2k:2m; s1Ãꢀ j‡1† are called b, c, d, respectively.
The site following d is called e.
Ã
.
.
This situation is depicted in Fig. 1.

224
K. Moizumi and G. Cybenko
Fig. 1. De®nition of sites a; b; c; d; e.
Now suppose that the ®ve sites, a; b; c; d; e, form part of the optimal tour. Our
goal is to show that
t1Ãj
t1j ‡ p1jL100 ‡ ꢀ1 À p1j†L1
p1j
tb
ˆ
ˆ
pb
p1j
t1Ãꢀ j‡1†
p1ꢀ j‡1†
t1ꢀ j‡1† ‡ p1ꢀ j‡1†L100 ‡ ꢀ1 À p1ꢀ j‡1††L1
td
U
ˆ
ˆ
pd
p1ꢀ j‡1†
:
We do this in two steps:
1. Showing that tb=pb U tc=pc.
2. Showing that tc=pc U td=pd .
Step 1. Let the cost of the optimal tour with the subsequence a; b; c; d; e be Cabcde
and consider the cost of the tour with sites b and c switched. Let the cost of the
tour with b and c switched be Cacbde. Then by optimality
0 V Cabcde À Cacbde
ˆ P Á fLx0 1 ‡ ꢀt1j ‡ pbL100 ‡ ꢀ1 À pb†L102† ‡ ꢀ1 À pb†ꢀtc0 ‡ pcL200 ‡ ꢀ1 À pc†L201†
À Lx0 2 À ꢀtc0 ‡ pcL200 ‡ ꢀ1 À pc†L201† À ꢀ1 À pc†ꢀt1j ‡ pbL100 ‡ ꢀ1 À pb†L1†g
ˆ X V X À P Á ꢀLx0 1 À Lx0 2 ‡ L201 À L1†;
P
Q
m
sˆk‡1
sÀ1
where
pb ˆ p1j,
pc ˆ pms
,
and tc0 ˆ t2k
‡
jˆk ꢀ1 À p2j†t2s ‡
2k:2m
P
Q
mÀ1
sÀ1
jˆk ꢀ1 À p2j†L2.
sˆk‡1
Here P > 0 is the probability that failure has occurred at all nodes preceding b
in the tour so that we in fact visit b. Lx0 1 and Lx0 2 are the latencies from a to b and
d respectively since a can be either in S1, S2, or s0, the home site.
Note that once we arrive at d, the remaining costs are identical for both tours
and therefore cancel each other in the di¨erence. The term L102 À L1 arises as the
di¨erence in latencies in going from a to b versus a to c.

The Traveling Agent Problem
225
Finally, we note that Lx0 1 À Lx0 2 ‡ L102 À L1 is:
1. When x ˆ 1,
L1 À L102 À L102 À L1 ˆ 0:
2. When x ˆ 2,
L201 À L2 ‡ L102 À L1 ˆ L1 ‡ 2L12 ‡ L2 V 0:
3. When x ˆ 0, using the assumption L02 U L01 ‡ L12;
L001 À L002 ‡ L102 À L1 ˆ L01 ‡ L1 À L02 ‡ L12 V L1 V 0:
Thus, Lx0 1 À Lx0 2 ‡ L102 À L1 is nonnegative independent of the value of x. This
explains the last inequality. ꢀIt is this step that changes under Assumption 2A,
leading to slightly di¨erent inequalities but the same conclusion.)
Continuing, we have
0 V X À P Á ꢀLx0 1 À Lx0 2 ‡ L102 À L1†
ˆ P Á fꢀt1j ‡ pbL100 ‡ ꢀ1 À pb†L1†
‡ ꢀ1 À pb†ꢀL102 À L1 ‡ tc0 ‡ pcL200 ‡ ꢀ1 À pc†L102†
À ꢀL102 À L1 ‡ tc0 ‡ pcL200 ‡ ꢀ1 À pc†L201†
À ꢀ1 À pc†ꢀt1j ‡ pbL100 ‡ ꢀ1 À pb†L1†g
ˆ P Á ꢀpct1Ãj À pbtms
ˆ P Á ꢀpctb À pbtc†;
†
2k:2m
where tc ˆ tms
.
2k:2m
Thus, tb=pb U tc=pc as claimed.
Step 2. We now switch c and d in an optimal tour as above, and with the same
notational conventions, we have
0 V Cabcde À Cabdce
ˆ P Á fꢀL102 À L1 ‡ tc0 ‡ pcL200 ‡ ꢀ1 À pc†L102†
‡ ꢀ1 À pc†ꢀt1ꢀj‡1† ‡ pd L100 ‡ ꢀ1 À pd†L10x†
À ꢀt1ꢀj‡1† ‡ pd L100 ‡ ꢀ1 À pd†L102† À ꢀ1 À pd†ꢀtc0 ‡ pcL200 ‡ ꢀ1 À pc†L20xg
ˆ X 0 V X 0 À P Á ꢀ1 À pc†ꢀ1 À pd†ꢀL10x À L20x ‡ L102 À L1†
ˆ P Á ꢀpdtms2k:2m À pct1Ãꢀ j‡1†
ˆ P Á ꢀpdtc À pctd†;
†
where pd ˆ p1ꢀ j‡1†
.
Thus, tc=pc U td=pd. Again, L10x À L20x ‡ L102 À L1 is nonnegative as in step 1.
The two inequalities derived from steps 1 and 2 combine to show that if abcde
is part of the optimal tour, then tb=pb U tc=pc U td =pd as claimed.

226
K. Moizumi and G. Cybenko
Assertion 2. The TAP of Theorem 3 can be solved in Oꢀꢀn1 ‡ 1†ꢀn2 ‡ 1†† time
using dynamic programming after the nodes are sorted as speci®ed in step 1 which
requires Oꢀn1 log n1 ‡ n2 log n2† steps.
By Assertion 1, we can assume that the nodes have been ordered into the
required sequence which dictates the order in which they are visited in each sub-
network. We de®ne a Markov Decision Problem ꢀMDP) with states
S ˆ fꢀi; j; k† j 0 U i U n1; 0 U j U n2; k ˆ 1 or 2g W fFg;
where state ꢀi; j; k† means that an agent has already visited sites s11; . . . ; s1i and
s21; . . . ; s2j and is presently on subnetwork k. The terminal state is F. The states
ꢀ0; 0; 1† and ꢀ0; 0; 2† are the same initial state.
For instance, ꢀ0; 3; 2† means that sites s21; s22; s23 have been visited and the
agent is at subnetwork 2 while no sites from subnetwork 1 have yet been visited.
In the MDP framework, we need to describe actions for each state, corre-
sponding transition probabilities, and immediate costs. For the state ꢀi; j; 1† there
are two possible actions: G1 and G2, meaning attempt to go to the next site in
subnet 1 or subnet 2. For state ꢀi; j; 1† and action G1 the next state is ꢀi ‡ 1; j; 1†
with probability ꢀ1 À p1i† and F with probability p1i. The expected immediate
cost is
t1i ‡ p1iL100 ‡ ꢀ1 À p1i†L1:
For state ꢀi; j; 1† and action G2, the next state is ꢀi; j ‡ 1; 2† with probability
ꢀ1 À p2j† and F with probability p2j. The expected immediate cost is
t2j ‡ p2jL200 ‡ ꢀ1 À p2j†L12:
The same de®nitions apply to states ꢀi; j; 2† with actions G1 and G2 as above with
appropriate changes.
For states ꢀn1; j; k† the only allowable action is G2 and for states ꢀi; n2; k† the
only allowable actions are G1. For state ꢀn1; n2; k† there is only one action, to go
to the terminal state F with appropriate costs.
This MDP has no cycles and so the optimal cost-to-go values can be computed
using backtracking from the terminal node in time proportional to the total num-
ber of states which is 2ꢀn1 ‡ 1†ꢀn2 ‡ 1† ‡ 1.
9
2.3. Extensions and Discussion
The above algorithm and results apply to situations with multiple subnetworks
providing that internetwork latencies and latencies to the home site are larger that
internetwork latencies which are constant. In that case, the algorithm requires
time
mꢀn1 ‡ 1†ꢀn2 ‡ 1† Á Á Á ꢀnm ‡ 1† ‡ 1
for m subnetworks. In the case where ni ˆ 1, this reduces to the general case of
the TAP which is NP-Hard and the algorithm is exponential.
We can use these results as approximation methods for general TAPs by

The Traveling Agent Problem
227
organizing subnetworks with constant latencies that approximate the original
latencies.
We have shown that the TAP is NP-complete in the general formulation.
However, by clustering multiple sites and approximating latencies among them to
be constant, the complexity of the problem is decreased into a polynomial time
computation.
The problems dealt with in this paper assume that ꢀ1) a single agent executes
a task and that ꢀ2) network properties are static. In many cases, a task can be
®nished in a shorter time by multiple agents rather than a single agent. The TAP
has been extended to the case where multiple agents are involved in the same task
[M2]. Network properties tend not to be static in real life, and even not to be
stationary. Replanning in the case of changing network statistics can be a solution
to the second problem.
3. The Traveling Agent Problem with Deadlines
The above results are relevant to agent planning problems without deadline. In
this section we address the important problem of handling a deadline for each site
ꢀthe Traveling Agent Problem with Deadlines). For example, agents encounter
this situation when they have information about when sites are going to shutdown
or be isolated due to link disconnection. The goal of the problem is to obtain
tours that ®nish an agent's task with the highest probability of success before
machines become unusable. We present a pseudopolynomial algorithm for ®nding
such optimal tours below. Pseudopolynomial means polynomial with respect to
the values of the input, not the number of bits required to represent them [GJ].
Assumption 3. Each site i ꢀincluding the home site s0) has a deadline, Di, by which
time an agent must visit the site or else the site becomes unavailable.
Theorem 6. Assume in the TAP that l ˆ lij ˆ lkm V 0 for all i; j; k; m, namely As-
sumption 1. Compute times, ti, and probabilities, pi, can be arbitrary but l and ti are
integer. The agent must ®nish its task by visiting sites and returning to the home site
before the respective deadlines. The optimal tour for this TAP with Deadlines max-
imizes the probability of success without exceeding a deadline at each site. ꢀThe
deadline time Di is measured from the time the agent leaves the home site.) Such an
optimal tour can be computed in pseudopolynomial time using a dynamic program-
ming algorithm. Input times are assumed to be integer.
Proof. The proof consists of four steps. In the ®rst step we formalize the concept
of a task's completion before deadlines. The second step is an observation that in
order to avoid missing deadlines, sites should be visited in increasing order of
their deadlines. The third step introduces two arrays, eꢀj; s† and pꢀj; s†. The ®rst
array holds the boolean function which is true if there is a subset which consists of
the ®rst through jth sorted sites and which has the total time equal to s, without
violating any deadlines. The second array holds the total probability of success

228
K. Moizumi and G. Cybenko
pꢀj; s† of the subset that makes eꢀ j; s† ˆ true. The fourth step constructs these
arrays in pseudopolynomial time using dynamic programming. The optimal tour
is the sorted subset that maximizes pꢀj; s†.
Step 1. We formalize the meaning of a task's completion before deadlines in this
step. We assume that the agent start time is t ˆ 0 and that the agent must visit
site i before t ˆ Di. If an agent visits si, this means that it failed at every site
it visited before. The time to visit all sites before im for a tour T 0ꢀm† ˆ
hi1; i2; . . . ; imi where m U n is
m
X
0
CT ꢀm† ˆ l01 ‡ ti ‡
ꢀli
kÀ1ik
‡ ti †
1
k
kˆ2
m
X
ˆ
ꢀl ‡ ti †
k
kˆ1
m
X
ˆ m Á l ‡
ti :
k
kˆ1
0
The above CT ꢀm† can be no greater than the deadline Di at the site im and, in
m
addition, the total time for all tours T 0ꢀk† for k < m should not exceed the dead-
0
line Di . Although the order of visiting sites does not a¨ect the total time CT ꢀm†
k
and the total probability of success for the tour, the wrong order may violate the
deadline constraints.
The tour which maximizes the probability of successful completion can be
computed in pseudopolynomial time. The dynamic programming algorithm is as
shown in the following steps.
Step 2. Consider a tour T ˆ h1; 2; . . . ; ni with sites sorted according to
increasing deadlines. This tour has the minimum maximum tardiness where
the minimal maximal tardiness for a tour T à ˆ hi1; i2; . . . ; ini is de®ned to be
n
minT fmaxkˆ1ꢀCT0 à ꢀk† À D ; 0†g where C0 ꢀk† represents the completion time at
Ã
T Ã
ik
the ikth site as above. This result is derived from Jackson's work [J] and has the
following consequence that is critical in the proof: If one or more of the completion
times for a sequence of sites with increasing deadlines violate some deadline, then
every other ordering of that sequence will violate some deadline as well. This
follows from Jackson's result since the increasing deadline ordering minimizes the
maximal tardiness, which must be better than the tardiness of any other ordering.
Therefore, all other orderings have larger tardiness which by virtue of being pos-
itive means that some deadline is missed. Algorithmically, this means that we can
reject a sequence of sites if they are ordered by increasing deadlines and violate
some deadlineÐwe only need to check that ordering for infeasibility of the whole
set of sites.
Step 3. We introduce two arrays of size n ꢀnumber of sites) by minꢀB; D0 À l†
P
n
where B ˆ kˆ1 tk ‡ n Á l ꢀtotal possible time for visiting all sites) and D0 À l

The Traveling Agent Problem
229
represents the deadline that an agent should leave the last site for its home
machine.
For integer 1 U j U n, let eꢀj; s† ˆ 1 if there is a subset of f1; 2; . . . ; jg for
which the total maximum time is exactly s and each site of which can be visited
no later than its deadline. If such a subset does not exist, eꢀ j; s† ˆ 0 so e is essen-
tially Boolean. We also de®ne the array value pꢀj; s† ˆ 0 if eꢀj; s† ˆ 0 and pꢀ j; s†
Q
ˆ 1 À
ꢀ1 À pk† if eꢀj; s† ˆ 1. Here Teꢀj;s† is a set of sites which has the
k A Teꢀj; s†
following three properties: ꢀ1) the sum of the times of the members is s ꢀthus
making the deadline constraint transparent); ꢀ2) Teꢀj;s† has the maximum proba-
bility of success among all the subsets which satisfy ꢀ1); and ꢀ3) each of the mem-
bers can be visited no later than the deadline corresponding to that site. That
probability is precisely what is stored in pꢀj; s†.
Step 4. The values of eꢀj; s† and pꢀj; s† are obtained by dynamic programming.
The dimensions of the arrays e and p are both n by minꢀB; D0 À l†. They are
initialized to be all 0.
We start the algorithm with the row j ˆ 1 and proceed to calculate the follow-
ing rows of e from the previous rows. For j ˆ 1, eꢀ1; s† ˆ 1 if and only if either
s ˆ 0, or s ˆ l ‡ t1 and s U D1. If eꢀ1; s† ˆ 0, or eꢀ1; s† ˆ 1 and s ˆ 0, pꢀ1; s† is set
to be 0. If eꢀj; s† ˆ 1 and s ˆ l ‡ t1, then pꢀj; s† ˆ p1 ˆ 1 À ꢀ1 À p1†.
For j V 2, we set the value of eꢀj; s† ˆ 1 if and only if at least of the following
hold: ꢀ1) eꢀ j À 1; s† ˆ 1 is true; ꢀ2) l ‡ t j U s and eꢀj À 1; s À l À t j† ˆ 1 where
s U Dj; or ꢀ3) l ‡ tj ˆ s. This means that we can construct a tour with total cost s
in the case of failure in one of three possible ways:
1. There was already a tour involving sites 1; 2; . . . ; j À 1 with total time s
ꢀthe case eꢀj À 1; s† ˆ 1), each site of which can be visited no later than its
deadline.
2. There is a nonempty tour with total time s À tj À l involving a subset of sites
1; 2; . . . ; j À 1 and we can add the site j to that tour if s U Dj ꢀthis is the case
eꢀ j À 1; s À tj À l† ˆ 1 and l ‡ tj U s where s U Dj).
3. l ‡ tj ˆ s and so we have a tour with only the site j on it if s U Dj.
In the second case, we check that if we can add the site j to a tour by compar-
ing s and Dj when eꢀj À 1; s À l À tj† ˆ 1 and l ‡ tj U s. It is obvious that a tour
which satis®es eꢀj À 1; s À l À tj† ˆ 1 has a maximum tardiness 0 since the tour
does not violate the deadline constraints. Now if we append the site j at the end
of the tour, the total time becomes s. The maximum tardiness of sites in the new
tour is maxf0; s À Djg because those sites are sorted in increasing order of their
deadlines. Since the maximum tardiness is minimum among those of all possible
permutations of sites in the tour, it is impossible to decrease the maximum tardi-
ness by changing the order of sites in the tour. Thus, site j cannot be added to a
tour that satis®es eꢀj; s† ˆ 1 if s > Dj.
We also de®ne elements of the jth row of p as follows. If eꢀj; s† ˆ 0, pꢀj; s† ˆ
0. We handle the cases for which eꢀj; s† ˆ 1 in the following way:
1. There was a tour already involving a subset of 1; 2; . . . ; j À 1 with a total
time of s, each site of which can be visited no later than its deadline but j

230
K. Moizumi and G. Cybenko
could not be added to any previous tour to get a new tour ꢀcase for which
eꢀ j À 1; s† ˆ 1 but eꢀj À 1; s À tj À l† ˆ 0): pꢀj; s† ˆ pꢀj À 1; s†.
2. There was no tour with total time s based on sites 1; 2; . . . ; j À 1 but there is
one when sj is added to a tour ꢀcase when eꢀ j À 1; s† ˆ 0 and eꢀj À 1;
s À tj À l† ˆ 1): pꢀj; s† ˆ 1 À ꢀ1 À pj†ꢀ1 À pꢀj À 1; s À l À tj†† if s U Dj.
3. There was already a tour involving a subset of 1; 2; . . . ; j À 1 with a total
time of s and another tour with total time s À l À tj using sites 1; 2; . . . ; j À 1
which can be visited no later than their respective deadlines ꢀthe case
when eꢀj À 1; s† ˆ 1, and eꢀj À 1; s À tj À l† ˆ 1 and s U Dj): pꢀj; s† ˆ
maxfpꢀj À 1; s†; 1 À ꢀ1 À pj†ꢀ1 À pꢀ j À 1; s À l À tj††g.
4. s ˆ l ‡ tj, eꢀj À 1; s† ˆ 1 and s U Dj in which case pꢀj; s† ˆ
maxfpꢀj À 1; s†; pjg.
This handles all cases and clearly requires only a single scan of each row, there-
fore about OꢀminꢀD0 À l; B†† operations per row for n rows yielding a complexity
of OꢀminꢀD0 À l; B† Á n† steps.
The subset which maximizes the probability of the agent's success and whose
sites can be visited no later than their respective deadlines is the one that max-
imizes pꢀn; s† for s U D0 À l ꢀrecall that pꢀj; s† ˆ 0 if eꢀ j; s† ˆ 0). D0 À l is the
deadline by which time an agent has to leave the last site for its home site 0. By
visiting all the sites in that subset in increasing order of their deadline, no exceed-
ing of deadlines will occur. However, this order cannot guarantee the minimum
expected time in visiting all the sites no later than their respective deadlines.
It takes at most n log n to sort the subset in increasing order of deadlines.
Therefore, the optimal solution can be obtained in time that is polynomial at most
P
n
in n and B, Oꢀ2 Á n Á minf kˆ1 tk ‡ n Á l; D0 À lg ‡ n log n†.
The only remaining issue is that of maintaining the list of sites on a tour corre-
sponding to eꢀj; s† ˆ 1 and the value of pꢀj; s† recorded in the array. This can
clearly be handled within the time bounds we have demonstrated.
9
As mentioned above, this solution for TAP with deadlines optimizes the proba-
bility of success but does not necessarily minimize the expected time to visit all
sites on the tour while satisfying the respective deadlines. Note that the maximal
probability tour subject to the deadline constraints may not have a minimal
expected time of completion. E½cient algorithms for actually minimizing the
expected time appear to be di½cult to obtain and remains an open problem to our
knowledge, even in the sense of pseudopolynomial performance.
4. Conclusion
Mobile agents have received much attention recently as a way to access dis-
tributed resources in a low bandwidth network e½ciently. Planning is a required
capability so that agents can make the best use of available resources. This paper
proposes a planning problem for mobile agents that is often observed in infor-
mation retrieval and data-mining applications. The problem is to ®nd the best
sequence of locations so that an agent can ®nd desired information in minimum

The Traveling Agent Problem
231
time if there are several possible sites that may contain the information with some
probability, and network statistics such as latency, bandwidth, and machine load
are available. We prove that the complexity of the problem is NP-complete in the
general formulation but have successfully reduced the complexity to be poly-
nomial time by employing realistic subnetwork assumptions. E½cient algorithms
for maximizing probabilities of success in the presence of deadlines are also dem-
onstrated. Further investigation on the planning problem where multiple agents
cooperate with each other to complete a same task is available at [M2].
Acknowledgments. The authors thank D. Bertsekas and S. Patek for pointing
out related work and references.
References
[AIS] J. Ambros-Ingerson and S. Steel. Integrating planning, execution and monitoring, Proceedings
of the Seventh National Conference on Arti®cial Intelligence 6AAAI-88), Morgan Kaufmann,
St. Paul, MN, 1988.
[B1] Richard E. Bellman. Dynamic Programming, Princeton University Press, Princeton, NJ, 1957.
[B2] D. M. Bertsekas. Dynamic Programming, Prentice-Hall, Englewood Cli¨s, NJ, 1987.
[B3] D. M. Bertsekas. Dynamic Programming and Optimal Control, Athena Scienti®c, Belmont,
MA, 1995.
[CT] K. W. Currie and A. Tate. O-plan: the open planning architecture, Arti®cial Intelligence,
52ꢀ1), 1991.
[CGM] G. Cybenko, R. Gray, and K. Moizumi. Q-learning: a tutorial and extensions, in Mathematics
of Neural Networks, Kluwer, Boston, MA, 1997.
[DF] V. Decugis and J. Ferber. Action selection in an autonomous agent with a hierarchical dis-
tributed reactive planning architecture, Proceedings of the Second International Conference on
Autonomous Agent, Minneapolis/St. Paul, MN, 1998.
[DB] M. Drummond and J. Bresina. Anytime synthetic projection: maximizing the probability of
goal satisfaction, Proceedings of AAAI-90, Boston, MA, 1990
[FN] R. E. Fikes and N. J. Nilsson. STRIPS: a new approach to the application of theorem proving
to problem solving, Arti®cial Intelligence, 2ꢀ3±4), 1971.
[GJ] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-
Completeness, Freeman, San Francisco, CA, 1979.
[G] R. Gray. Agent Tcl: a ¯exible and secure mobile-agent system, Proceeding of the 1996 Tcl/Tk
Workshop, July 1996.
[H] R. A. Howard. Dynamic Programming and Markov Processes, MIT Press, Cambridge, MA,
1960.
[J] J. R. Jackson. Scheduling a Production Line to Minimize Maximum Tardiness, Research
Report 43, Management Science Research Project, University of California, Los Angeles, CA,
1955.
[JvRS] D. Johansen, R. van Renesse, and F. B. Scheidner. Operating system support for mobile
agents, Proceeding of the 5th IEEE Workshop on Hot Topics in Operating Systems, 1995.
[K] R. M. Karp. Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher
ꢀeds.), Complexity of Computer Computations, Plenum, New York, 1972.
[M1] P. Maes. Situated agents can have goals, Robotics and Autonomous Systems, 6:49±70, 1990.
[M2] K. Moizumi. The Mobile-Agent Planning Problem, Ph.D. Thesis, Thayer School of Engi-
neering, Dartmouth College, Hanover, NH, 1998. ꢀAvailable at http://actcomm.dartmouth.
edu/@papers/moizumi:thesis.ps.Z.)
[P] S. Patek. Ingress Planning in FASM, ALPHATECH Technical Report, Burlington, MA,
1997.

232
K. Moizumi and G. Cybenko
[RGK] D. Rus, R. Gray, and D. Kotz. Autonomous and adaptive agents that gather informationn,
Proceedings of the AAAI 96 International Workshop on Intelligent Adaptive Agents, August
1996.
[S] E. D. Sacerdoti. The nonlinear nature of plans, Proceedings of the Fourth International Joint
Conference on Arti®cial Intelligence 6IJCAL75), Tbilisi, Georgia, 1975.
[W] J. E. White. Telescript technology: The Foundation for the Electronic Marketplace, General
Magic White Paper, General Magic, 1994.