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.

The details of this achievement will be presented at the International Conference on Autonomous Agents and Multiagent Systems 2022 (hereinafter "AAMAS"), which will commence on May 9^th.

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 is 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.

図1 経路計算手法の比較

(a) Conventional method (grid)

(b) Conventional method (roadmap)

(c) Proposed method (CTRM)

Fig. 1: Comparison of grid, roadmap, and the proposed CTRM.

Legend: Black circles: obstacles, Blue circles: starting point of each agent, Blue squares: goal point of each agent

Fig. 2: Overview of the proposed method

Legend: Black circles: obstacles, colored circles: starting point of each agent, colored squares: goal point of each agent

Fig. 3: Example of planning results for 10 agents

(a) Conventional method (grid)

(b) Conventional method (roadmap)

(c) Proposed method (CTRM)

Fig. 3: Example of planning results for 10 agents

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)

About OMRON SINIC X Corporation
OMRON SINIC X Corporation is a strategic subsidiary seeking to realize the “near future designs” that OMRON forecasts. Researchers with cutting-edge knowledge and experience across many technological domains, including AI, Robotics, IoT, and sensing, are affiliated with OSX, and with the aim of solving social issues, they are working to create near future designs by integrating innovative technologies with business models and strategies in technology and IP. The company will also accelerate the creation of near future designs through joint research with universities and external research institutions. For more details, please refer to https://www.omron.com/sinicx/

■ For press inquiries related to this release, please contact the following:: Engagement Communication Department
Innovation Exploring Initiative HQ
OMRON Corporation
TEL: 0774-74-2010

OMRON SINIC X to present research paper in AAMAS2022, leading international conference on autonomous robots