OMRON Corporation (HQ: Shimogyo-Ku, Kyoto. President and CEO: Yoshihito Yamada) announced that researchers at OMRON SINIC X Corporation (HQ: Bunkyo-Ku, Tokyo. President and CEO: Masaki Suwa), a subsidiary of OMRON that aims to create a near future design, have developed a novel path search algorithm that leverages machine learning technologies to improve the path planning ability of autonomous mobile robots. The algorithm developed can learn from previous path planning problem instances to improve mobile robots’ efficiency in recognizing and exploring the environment in which they move. The details of this achievement were presented at the International Conference on Machine Learning (ICML) 2021 held from July 18^th to 24^th.

Along with NeurIPS^*1 and ICLR^*2, ICML is one of the premier international conferences bringing together researchers from around the world in the machine learning field. More than 5,000 research papers were submitted to the 2021 conference, and just 22% were accepted.

*1：Neural Information Processing Systems
*2：International Conference on Learning Representations

Background
Major changes in our lifestyles caused by the spread of COVID-19 have promoted a variety of proof-of-concept experiments for autonomous mobile robot (AMR) applications such as delivery and sterilization. In the domain of supply-chain management and transportation, which is struggling with an increasingly severe labor shortage, many researchers are working on projects that use AMRs to automate the last-mile delivery of packages from hubs to end users. In such cases, AMRs need to derive their moving path and make decisions autonomously in a diverse environment. Path planning is an important technique that allows AMRs to find the shortest path to arrive at their destinations while avoiding any collisions with surrounding obstacles.

Much research has been done on path planning algorithms. Many studies have utilized and extended the A* search algorithm as it can search for a shortest path from a start to a goal location efficiently. More recent work has sought to leverage deep learning techniques to further improve path planning ability by making AMRs learn from previous path planning demonstrations. Nevertheless, such approaches based on deep learning have still encountered performance issues such as suboptimality or insufficiency in finding a path.

Research overview
In this context, Ryo Yonetani (Principal Investigator at OSX), Tatsunori Taniai (Senior Researcher at OSX) and the team have proposed a novel algorithm named “differentiable A* search,” which is the first to extend the canonical A* search algorithm to be used as a module of a deep neural network^*3 and to substantially improve path planning performances.

*3：Deep neural networks generally refer to artificial neural networks with many internal computation layers.

＜Publication＞
Title:「Path Planning using Neural A* Search」
Authors: Ryo Yonetani (OSX), Tatsunori Taniai (OSX), Mohammadamin Barekatain (OSX Research Intern 2019-2020), Mai Nishimura (OSX), Asako Kanezaki (Tokyo Institute of Technology, OSX Technical Advisor)

Main Features:

Developed “differentiable A* search” that can be used as a part of deep neural networks
The research team reformulated a canonical A* search, a common approach to path planning, as a novel differentiable A* search so as to be compatible with back-propagation^*4 widely used in deep learning. This allowed them to use A* search as a module of deep neural networks and learn it to efficiently plan expected paths for given problem instances.

*4：Back-propagation is a machine learning algorithm to learn neural networks by minimizing the error between neural network outputs and supervised signals.

Overview of the proposed approach

Significantly improved the trade-off between optimality and efficiency in path planning
Solving path planning problems involves a trade-off between path optimality and efficiency, as deriving optimal paths in a given environment often requires an extensive exploration of valid paths in the environment. With the differentiable A* search, deep neural networks can learn the relationship between path planning problem instances and their solution paths. The research team confirmed that this learning led to a significant improvement of the optimality-efficiency trade-off over existing methods in a path planning benchmark test.

Performance evaluation results on a benchmark dataset

Each algorithm searches the gray area for a shortest path from a start to a goal location while avoiding obstacles annotated in black.
The proposed approach was able to plan shorter paths than existing methods as shown in red.
Furthermore, the proposed approach demonstrates higher search efficiency than the existing methods as it explored smaller regions annotated in green.

Existing method 1: best first search
Existing method 2: Choudhury, S., Bhardwaj, M., Arora, S., Kapoor, A., Ranade, G., Scherer, S., and Dey, D. Data-driven planning via imitation learning. The International Journal of Robotics Research (IJRR), 37(13-14):1632–1672, 2018.

Enabled path planning on raw image inputs
Typical A* search algorithms require prior knowledge about which parts of the environment are passable or impassable. On the other hand, the novel approach developed here can acquire such knowledge by learning from a dataset consisting of images of the environment taken by a camera and trajectories of pedestrians moving in the environment. This allows the planning of a path consistent with that of pedestrians without giving detailed image information about the environment such as the location of roads and buildings.

Evaluation results using real images
(Ground-truth trajectory was given by a path from the start point to the goal along the road while bypassing green trees.)

OMRON SINIC X believes that the path planning algorithm developed this time will provide an effective way for AMRs to move safety by observing and recognizing surrounding people and obstacles through a camera and avoiding them autonomously. Going forward, the company will seek to further improve the path planning algorithm while investigating its effectiveness using real AMRs. 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.

About OMRON SINIC X Corporation
OMRON SINIC X Corporation (OSX) 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 are working to create near future designs by integrating innovative technologies with business models and strategies in technology and IP. For more details, please refer tohttps://www.omron.com/sinicx/en/.

■ Contact from Media:: Engagement Communication Department
Innovation exploring Initiative Headquarters
OMRON Corporation
TEL: +81-77-474-2010

Research paper from OMRON SINIC X presented in top-tier international conference on machine learning research