International Journal of Control, Automation and Systems 2007; 5(3): 295-306
© The International Journal of Control, Automation, and Systems
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.
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.
Sang-Hoon Ji, Jeong-Sik Choi, and Beom-Hee Lee
Seoul National University, Korea
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.
Vol. 23, No. 2, pp. 359~682
Dae-Sung Jang, Doo-Hyun Cho, Woo-Cheol Lee, Seung-Keol Ryu, Byeongmin Jeong, Minji Hong, Minjo Jung, Minchae Kim, Minjoon Lee, SeungJae Lee, and Han-Lim Choi*
International Journal of Control, Automation, and Systems 2024; 22(8): 2341-2384Jiangping Wang, Shirong Liu*, Botao Zhang, and Changbin Yu
International Journal of Control, Automation and Systems 2021; 19(3): 1340-1351Anugrah K. Pamosoaji, Mingxu Piao, and Keum-Shik Hong*
International Journal of Control, Automation and Systems 2019; 17(10): 2610-2623