遺伝的プログラミングによるマルチロボット経路計画
Multi-Robot Path Planning Via Genetic Programming
遺伝的プログラミングを用いて単線ワークスペースでのマルチロボット経路計画問題を解き、従来の完全アルゴリズムより少ない時間ステップで解けるプログラムを生成した研究。
著者: Alexandre Trudeau, Christopher M. Clark
分類: cs.RO, cs.NE
原文アブストラクト
This paper presents a Genetic Programming (GP) approach to solving multi-robot path planning (MRPP) problems in single-lane workspaces, specifically those easily mapped to graph representations. GP's versatility enables this approach to produce programs optimizing for multiple attributes rather than a single attribute such as path length or completeness. When optimizing for the number of time steps needed to solve individual MRPP problems, the GP constructed programs outperformed complete MRPP algorithms, i.e. Push-Swap-Wait (PSW), by $54.1\%$. The GP constructed programs also consistently outperformed PSW in solving problems that did not meet PSW's completeness conditions. Furthermore, the GP constructed programs exhibited a greater capacity for scaling than PSW as the number of robots navigating within an MRPP environment increased. This research illustrates the benefits of using Genetic Programming for solving individual MRPP problems, including instances in which the number of robots exceeds the number of leaves in the tree-modeled workspace.