The traveling agent problem

This paper considers a sequencing problem which arises naturally in the sch eduling of software agents. We are given n sites at which a certain task mi ght be successfully performed. The probability of success is p(1) at the it h site and these probabilities are independent. Visiting site i and trying the task there requires time (or some other cost metric) t(1) whether succe ssful or not. Latencies between sites (i) and (j) are l(ij), that is, the t ravel time between those two sites. Should the task be successfully complet ed at a site then any remaining sites do not need to be visited, The Travel ing Agent Problem is to find the sequence which minimizes the expected time to complete the task. The general formulation of this problem is NP-Comple te. However, if the latencies are constant we show that the problem can be solved in polynomial time by sorting the ratios t(1)/p(1) according to incr easing value and visiting the sites in that order. This result then leads t o an efficient algorithm when groups of sites form subnets in which latenci es 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 deadl ines. Applications to mobile and intelligent agents are described.