The Traveling Agent Problem

 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 ith 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 Traveling 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 t _i/p _i according to increasing 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. Date received: February 10, 1998. Date revised: November 16, 1999.