Coordination of intelligent agents in real-time search

Search is a fundamental problem-solving method in artificial intelligence. Traditional off-line search algorithms attempt to find an optimal solution whereas real-time search algorithms try to find a suboptimal solution more quickly than traditional algorithms to meet real-time constraints. In this work, a new multi-agent real-time search algorithm is developed and its effectiveness is illustrated on a sample domain, namely maze problems. Searching agents can see their environment with a specified visual depth and hence can partially observe their environment. An agent makes use of its partial observation to select a next move, instead of using only one-move-ahead information. Furthermore agents cooperate through a marking mechanism to be able to search different parts of the search space. When an agent selects its next move, it marks its direction of move before executing the move. When another agent comes to this position, it sees this mark and, if possible, moves in a different direction than the previously selected direction. In this way, marking helps agents coordinate their moves with other agents. Although coordination brings an overhead, from experiments we observe that this mechanism is effective in both search time and solution length in maze problems.