Distributed Coordination of Mobile Agent Teams: The Advantage of Planning Ahead

Abstract

We consider the problem of coordinating a team of agents engaged in executing a set of inter-dependent, geographically dispersed tasks in an oversubscribed and uncertain environment. In such domains, where there are sequence-dependent setup activities (e.g., travel), we argue that there is inherent leverage to having agents maintain advance schedules. In the distributed problem solving setting we consider, each agent begins with a task itinerary, and, as execution unfolds and dynamics ensue (e.g., tasks fail, new tasks are discovered, etc.), agents must coordinate to extend and revise their plans accordingly. The team objective is to maximize the utility accrued from executed actions over a given time horizon. Our approach to solving this problem is based on distributed management of agent schedules. We describe an agent architecture that uses the synergy between intra-agent scheduling and inter-agent coordination to promote task allocation decisions that minimize travel time and maximize time available for utility-acrruing activities. Experimental results are presented that compare our agent's performance to that of an agent using an intelligent dispatching strategy previously shown to outperform our approach on synthetic, stateless, utility maximization problems. Across a range of problems involving a mix of situated and non-situated tasks our advance scheduling approach dominates this same dispatch strategy. Finally, we report performance results with an extension of the system on a limited set of field test experiments.