Developed a path planning method that enables multiple autonomous mobile robots to move efficiently
OMRON SINIC X Corporation (HQ: Bunkyo-Ku, Tokyo. President and CEO: Masaki Suwa; hereinafter “OSX”) has developed a new method that can significantly improve the efficiency of path planning for multiple autonomous mobile robots (hereinafter “agents”) to travel to their destinations without collision (hereinafter “multi-agent path planning”).
Most conventional methods for multi-agent path planning require agents to search for collision-free paths extensively in a large workspace. In contrast, our new method can reduce the search space for each agent by a factor of ten, while maintaining a success rate and solution quality comparable to conventional methods.
Advertisments
The details of this achievement was presented at the International Conference on Autonomous Agents and Multiagent Systems 2022 (hereinafter “AAMAS”), which commenced on May 9th.
AAMAS is an international conference where researchers from around the world participate in discussions and is one of the leading international conferences on autonomous robots. The presentation from OSX was scheduled for May 12 at 0am and 6pm JST (UTC+09).
＜Publication＞
Title: “CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces”
Authors: Keisuke Okumura (Tokyo Institute of Technology, OSX Research Intern Apr.-Oct. 2021), Ryo Yonetani (OSX), Mai Nishimura (OSX), Asako Kanezaki (Tokyo Institute of Technology, OSX Technical Advisor)
The features of the technology developed are as follows.
■ Background
In recent years, due to labor shortages in manufacturing sites and various other scenes such as the medical and service industries, there has been an accelerating trend toward the use of machines to replace human work and promote automation. With a particular demand to deliver goods to multiple destinations in the transportation sector, many novel technologies have been developed to utilize multiple autonomous mobile robots to improve work efficiency.
To enable multiple robots (agents) to efficiently reach their respective destinations, it is essential to solve a path planning (multi-agent path planning) problem to avoid obstacles and derive shorter travel paths without collisions between agents. A typical approach to multi-agent path planning is to represent the entire workspace agents can move as a grid map and then search for a path (Fig. 1(a)※1). Workspaces can also be regarded as a continuous space, assuming that agents can move more flexibly on a roadmap, a graph consisting of random locations (vertices) agents can stay (Fig. 2(b)※2). Either way, however, grid maps and roadmaps should be dense enough to derive short travel paths, which in turn increases the computational cost of path planning.
※１ e.g, David Silver. 2005. Cooperative Pathfinding. Proceedings of the Artificial Intelligence for Interactive Digital Entertainment Conference (AIIDE) (2005), 117–122
※２ e.g, Wolfgang Hönig, James A Preiss, TK Satish Kumar, Gaurav S Sukhatme, and Nora Ayanian. 2018. Trajectory Planning for Quadrotor Swarms. IEEE Transactions on Robotics (T-RO) 34, 4 (2018), 856–869.
■ Research overview
The OSX research group proposed cooperative timed roadmaps (CTRM) to address these challenges. CTRM can efficiently limit the search space for each agent to find a path to its own goal while avoiding obstacles and other Agents (Fig. 1(c)).
CTRM can be constructed effectively by leveraging machine learning techniques. Given a collection of multi-agent path planning problem instances and their solutions prepared in advance, the proposed method learns a probability distribution of each agent’s movement to avoid collisions and cooperatively move toward their destination while taking into account obstacles and other agents’ positions. The learned distribution can then be used for a new, previously unseen path planning problem instance to construct CTRMs while eliminating redundant locations unrelated to possibly solution paths (Fig. 2). As a concrete example, for 30 to 40 agents moving in an environment with several obstacles, using CTRMs can reduce the search space by about one-tenth and the computation time by about one-half to produce paths of comparable quality to conventional methods. Fig. 3 shows an example of path planning results for each method with 10 agents. The proposed method makes it possible to find a smooth and efficient path solution in a short time.
The newly developed method is expected to be used in various applications of multi-agent path planning, such as automation of logistics warehouses and cooperative control of drones and other vehicles. Going forward, the company will continue to verify the method using real autonomous mobile robots, aiming for further improvements in accuracy and calculation efficiency. Through these research activities, the company will continue to contribute open innovations through collaborations with external research institutes, strive for solutions to social issues, and explore new social needs.
The results of this study are released as open-source software and are available at the following links.
https://github.com/omron-sinicx/ctrm
https://github.com/omron-sinicx/jaxmapp
For more information, please refer to the following article.
CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces (AAMAS 2022)
CLICK HERE FOR LATEST NEWS.
READ CURRENT AND PAST ISSUES OF IAA.
KEEP YOURSELF UPDATED, SUBSCRIBE TO IAA NOW!
AND DON’T FORGET FOLLOW US ON FACEBOOK, LINKEDIN AND TWITTER!