A system for multi-agent coordination in uncertain environments
This paper present a multi-agent architecture for coordinating large numbers of mobile agents (e.g. robots) cooperating in uncertain environments. In particular, the Canadian Traveler Problem (CTP) is the problem of nding a shortest path to a goal location in a graph, where individual edges of the graph might or might not be traversable[1]. The agent has an initial probabilistic knowledge about the states of the edges. Whether or not an edge is traversable can only be found out by moving there. Hence, an optimal solution to a CTP is a contingency plan, which o ers alternative routes if edges are not available. Finding an optimal contingency plan is known to be NP-hard. We focus on the multi-agent CTP, which involves multiple agents attempting to reach multiple target locations. Finding an optimal solution is even harder, since the space of actions at each point in time is exponential in the number of agents. Our multi-agent architecture approaches the above mentioned set of intractable problems in an eÆcient, real-time manner. The architecture supports a large number of mobile, goal-driven information agents that strive to maximize their reward for reaching goals. These agents are coordinated at a higher level by dispatcher agents whose purpose is to maximize the total reward accumulated over time. Extensive experimental results have been obtained in the context of natural disaster relief. Our experiments have been carried out in a realistic simulation of Honduras after Hurricane Mitch destroyed most of the country's infrastructure.