OMRON SINIC X Corp. has developed a new method that can significantly improve the efficiency of path planning for multiple autonomous mobile robots (AMRs) to travel to their destinations without collision. This is also called multi-agent path planning.

Most conventional methods for multi-agent path planning require AMRs to search for collision-free paths extensively in a large workspace. In contrast, the new method can reduce the search space for each agent by a factor of ten. During this process, it can maintain 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 (AAMAS).

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

Technology Features

Background

In recent years, labor shortages in manufacturing sites and various other scenes, such as the medical and service industries, are ever present. Thus, there has been an accelerating trend toward the use of machines to replace human work and promote automation. Specifically, there is a particular demand to deliver goods to multiple destinations in the transportation sector. Eventually, many novel technologies have been developed to utilize multiple autonomous mobile robots to improve work efficiency.

To enable multiple robots to efficiently reach their respective destinations, it is essential to solve a 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 that can move as a grid map and then search for a path (Fig. 1(a)¹). 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)²). 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.

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. 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. This is accomplished on the premise that a collection of multi-agent path planning problem instances and their solutions prepared in advance.

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

Publication

The article is titled “CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces” by 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 results of this study are released as open-source software and are available at the following links https://github.com/omron-sinicx/ctrm and https://github.com/omron-sinicx/jaxmapp.

Reference:

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