著者

北村 泰彦 寺西 憲一 辰巳 昭治 Yasuhiko Kitamura Ken-ichi Teranishi Shoji Tatsumi

雑誌

人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence (ISSN:09128085)

巻号頁・発行日

vol.11, no.3, pp.470-477, 1996-05-01

参考文献数

9

被引用文献数

7

---

Real-Time A^*(RTA^*) is an on-line search scheme in which look-ahead searches and moves are interleaved. It does not guarantee to find an optimal solution but it finds a semi-optimal solution with less search effort. To improve the quality of solution, Knight has proposed Multi-Agent Real Time A^*(MARTA^*), in which multiple agents concurrently and autonomously execute RTA^* for a given problem. In this scheme, agents do not coordinate their moves, but each agent just randomly chooses its move when the candidates look equally good. In this paper, we have interest in how agents should coordinate their moves to find a better solution faster. We propose two organizational approaches based on scattering and gathering. Each agent measures the distances from other agents and chooses its move in the direction of departing or approaching. These two approaches strengthen the discovery effect to find more undiscovered solutions and the learning effect to find more good solutions of MARTA^* respectively. We evaluate them through simulation experiments on maze and 15-puzzle problems and analyze why they work well or not from a point of heuristic depression, which is a local hollow of heuristic state evaluation values on paths to goal states. Once an agent falls into a depression, it cannot escape without filling in the depression, namely updating the state evaluation values. In a maze problem, in which deep depressions are scattered in its state space, scattered agents show better performance than gathered agents because less agents fall into depressions. On the other hand, in a 15-puzzle problem, in which shallow depressions are ubiquitous, gathered agents show better performance because they are better at cooperating to fill in the depressions. As a result, it is shown that we can get better search performance in MARTA^* by using an appropriate organization of agents depending on the characteristic of heuristic depressions of the given problem.