Regular Papers

International Journal of Control, Automation and Systems 2007; 5(3): 295-306

© The International Journal of Control, Automation, and Systems

A Computational Interactive Approach to Multi-agent Motion Planning

Sang-Hoon Ji, Jeong-Sik Choi, and Beom-Hee Lee

Seoul National University, Korea

Abstract

It is well known that mathematical solutions for multi-agent planning problems are very difficult to obtain due to the complexity of mutual interactions among multi-agents. Most of the past research results are thus based on the probabilistic completeness. However, the practicality and effectiveness of the solution from the probabilistic completeness is significantly reduced by heavy computational burden. In this paper, we propose a practically applicable solution technique for multi-agent planning problems, which assures a reasonable computation time and a real world application for more than 3 multi-agents, for the case of general shaped paths in agent movement. First, to reduce the computation time, an extended collision map is developed and utilized for detecting potential collisions and obtaining collision-free solutions for multi-agents. Second, a priority for multi-agents is considered for successive and interactive modifications of the agent movements with lower priority. Various solutions using speed reduction and time delay of the relevant agents are investigated and compared in terms of the computation time. A practical implementation is finally provided for three different types of agents to emphasize the effectiveness of the proposed interactive approach to multi-agent planning problems.

Keywords Computational approach, extended collision map, motion planning, multi-agents.

Article

Regular Papers

International Journal of Control, Automation and Systems 2007; 5(3): 295-306

Published online June 1, 2007

Copyright © The International Journal of Control, Automation, and Systems.

A Computational Interactive Approach to Multi-agent Motion Planning

Sang-Hoon Ji, Jeong-Sik Choi, and Beom-Hee Lee

Seoul National University, Korea

Abstract

It is well known that mathematical solutions for multi-agent planning problems are very difficult to obtain due to the complexity of mutual interactions among multi-agents. Most of the past research results are thus based on the probabilistic completeness. However, the practicality and effectiveness of the solution from the probabilistic completeness is significantly reduced by heavy computational burden. In this paper, we propose a practically applicable solution technique for multi-agent planning problems, which assures a reasonable computation time and a real world application for more than 3 multi-agents, for the case of general shaped paths in agent movement. First, to reduce the computation time, an extended collision map is developed and utilized for detecting potential collisions and obtaining collision-free solutions for multi-agents. Second, a priority for multi-agents is considered for successive and interactive modifications of the agent movements with lower priority. Various solutions using speed reduction and time delay of the relevant agents are investigated and compared in terms of the computation time. A practical implementation is finally provided for three different types of agents to emphasize the effectiveness of the proposed interactive approach to multi-agent planning problems.

Keywords: Computational approach, extended collision map, motion planning, multi-agents.

IJCAS
February 2025

Vol. 23, No. 2, pp. 359~682

Stats or Metrics

Share this article on

  • line

Related articles in IJCAS

IJCAS

eISSN 2005-4092
pISSN 1598-6446