Extending real-time heuristic search Part II: Heterogeneous multi-agent systems

Abstract

In Part I of this paper, DMHLRTA* (Dynamic Multi-Heuristic Learning Real-Time A*), an extension of real-time search methods to dynamically changing goal sets, was introduced. In this second part, another extension is proposed, which allows agents having different capabilities to cooperatively solve problems in real-time. A new search problem called real-time heterogeneous search is thus introduced. Unlike in previously proposed techniques, the agents here may differ in the type of actions they can execute. First of all, a formal definition of the problem is given as well as a trivial solution in which the agents use existing real-time search techniques. This solution is shown to be simple but inefficient. HMALRTA* (Heterogeneous Multi-Agent Learning Real-Time A*), is proposed as an alternative to this solution by allowing the agents to share the temporary goals that are created during the search; DMHLRTA* is used as part of HMALRTA* to search for the generated temporary goals. HMALRTA* does not introduce any coordination overhead nor does it require the agents to know the capabilities of each other, which makes it well-suited to parallelization and fault tolerant. HMALRTA* with upper bound is a variant of HMALRTA* in which an upper bound to the number of simultaneous temporary goals is imposed. The experimental results show that this algorithm reduces both computation requirement and the number of moves compared to the original HMALRTA*.