Graph Neural Network Based Method for Path Planning Problem
Sampling-based path planning is a widely used method in robotics,
particularly in high-dimensional state space. Among the whole process of the
path planning, collision detection is the most time-consuming operation. In
this paper, we propose a learning-based path planning method that aims to
reduce the number of collision detection. We develop an efficient neural
network model based on Graph Neural Networks (GNN) and use the environment map
as input. The model outputs weights for each neighbor based on the input and
current vertex information, which are used to guide the planner in avoiding
obstacles. We evaluate the proposed method's efficiency through simulated
random worlds and real-world experiments, respectively. The results demonstrate
that the proposed method significantly reduces the number of collision
detection and improves the path planning speed in high-dimensional
environments.
Xingrong Diao, Wenzheng Chi, Jiankun Wang
# Graph Neural Network Based Method for Path Planning Problem

###### Abstract

Sampling-based path planning is a widely used method in robotics, particularly in high-dimensional state space. Among the whole process of path planning, collision detection is the most time-consuming operation. In this paper, we propose a learning-based path planning method that aims to reduce the number of collision detections. We develop an efficient neural network model based on Graph Neural Networks (GNN). The model outputs weights for each neighbor based on the obstacle, searched path, and random geometric graph, which are used to guide the planner in avoiding obstacles. We evaluate the proposed method's efficiency through simulated random worlds and real-world experiments, respectively. The results demonstrate that the proposed method significantly reduces the number of collision detections and improves the path planning speed in high-dimensional environments.

 Graph Neural Network (GNN), Collision detection, Sampling-based path planning.

## I Introduction

The path planning problem in robotics is to find a collision-free path from the initial state and the goal state of a robot, given a description of the environment. In recent decades, graph-search and sampling-based methods have become two popular techniques for path planning problems in robotics. Graph-search methods, such as Dijkstra [1] and A* [2], usually search in discrete space, and the quality of their solution is often related to the degree of discretization. However, as the dimension of configuration space grows, these methods often fall into the curse of dimensionality [3], making them computationally difficult. In contrast, sampling-based methods such as Probabilistic Roadmap (PRM) [4], Rapidly-exploring Random Tree (RRT) [5], and Expansive Space Trees (EST) [6] improve efficiency and scalability in high-dimensional spaces by avoiding discretization and explicit representation of the configuration space. They explore the whole space by random sampling, resulting in probabilistic completeness for the feasible solution. Some sampling-based methods use graph-search methods concepts to find the path, such as Fast Marching Trees (FMT*) [7] and Batch Informed Trees (BIT*) [8]. FMT* and BIT* use the heuristic function to sort the samples and edges to explore, which improves the initial solution and convergence rate to the optimum.

Many sampling-based methods are improved by modifying the sampling distribution, such as Gaussian PRM [9], and GAN-Based heuristic RRT [10]. However, for most existing methods, collision detection is a major computational bottleneck because they need to repeatedly check the path to ensure that the path is collision-free. Typically, a path planning method spends about 70% of the computation time on collision detection. Lazy PRM [22] reduces collision detection by checking the edge only when it is on the global shortest path. Although it is useful in high dimensions, it does not guarantee robustness.

To address the aforementioned issues, we propose a learning-based path planning method for reducing the number of collision detections. Our method uses a graph neural network (GNN) model to predict the edge weights of the neighbor set of the current vertex. The weights are used to guide the planner to avoid obstacles and accelerate the search process. We evaluate the proposed method in simulations and real-world experiments and obtain good performance. Compared with classical path planning problems, our method significantly improves the path planning speed, reduces the number of collision detection, and improves the success rate and robustness in a high-dimensional environment.

Our main contributions include:

1) Propose a heuristic method for sampling-based path planning with GNN.

2) Design a GNN model to predict weights for each node in the neighbor set of the current vertex.

Fig. 1: Demonstrations for our method in 7D environment. The collision check of our method is 0.94 times and 0.0049 times of BIT* and PRM, respectively. The planning time of our method is 1.4% and 1.1% of the BIT* and PRM, respectively. From Left to Right: (a) GNN model. (b) BIT*