Neural Kinodynamic Planning: Learning for Kinodynamic Tree Expansion

We integrate neural networks into kinodynamic motion planning and present the Learning for KinoDynamic Tree Expansion (L4KDE) method. Tree-based planning ap- proaches, such as rapidly exploring random tree (RRT), are the dominant approach to finding globally optimal plans in contin- uous state-space motion planning. Central to these approaches is tree expansion, the procedure in which new nodes are added to an ever-expanding tree. We study the kinodynamic variants of tree-based planning, where we have known system dynamics and kinematic constraints. In the interest of quickly selecting nodes to connect newly sampled coordinates, existing methods typically cannot optimise the finding of nodes that have a low cost to transition to sampled coordinates. Instead, they use metrics like Euclidean distance between coordinates as a heuristic for selecting candidate nodes to connect to the search tree. We propose L4KDE to address this issue. L4KDE uses a neural network to predict transition costs between queried states, which can be efficiently computed in batch, providing much higher quality estimates of transition cost compared to commonly used heuristics while maintaining almost-surely asymptotic op- timality guarantee. We empirically demonstrate the significant performance improvement provided by L4KDE on a variety of challenging system dynamics, with the ability to generalise across different instances of the same model class and in conjunction with a suite of modern tree-based motion planners. I. I N T RO D U C T I O N This paper seeks to integrate neural network-based learning into kinodynamic motion planning. We focus on asymptoti- cally optimal, kinodynamic motion planning, where one aims to find a globally optimal plan between the start and goal coordinates while remaining both (1) collision-free and (2) compliant with the kinodynamic constraints of the robot or control system. When the search-space is continuous, kino- dynamic variants of tree-based motion planning algorithms are often the main workhorse for tackling these problems. Existing tree-based methods often consider both collision and kinodynamic constraints jointly during the motion planning procedure. However, if one disentangles the two constraints, one notices that collision constraints are environment-specific. In contrast, kinodynamic constraints are inherited from the robot hardware and do not vary over different planning tasks. Our motivation stems from the critical need for efficient and globally optimal motion planning in the context of kin- odynamic systems. Kinodynamic motion planning is a fun- damental problem in robotics. Robots must navigate through complex environments while adhering to collision avoidance and kinematic constraints. Achieving this balance is essential ∗Correspondence to tin.lai@sydney.edu.au †School of Com- puter Science, The University of Sydney, Australia. §Fait Corporation, Aus- tralia. ∼Robotics Institute, Carnegie Mellon University. ‡School of Comput- ing, University of Utah. £NVIDIA, USA. for real-world applications like autonomous vehicles, indus- trial robots, and humanoid robots. In particular, unlike the assumption of holonomic robots, practical, real-world robots are often subjected to some form of kinodynamic constraints. The choice of nodes directly impacts the efficiency and quality of the resulting motion plan, where existing methods typically rely on simplistic heuristics, like Euclidean distance, to guide node selection. By providing a more accurate estima- tion of state-transition cost, tree expansion can often benefit from successful and realistic distance estimation during state forward propagation, thereby expanding the capabilities of kinodynamic planners. With this insight, we integrate neural networks into the planning process and contribute the Learning for KinoDynamic Tree Expansion (L4KDE) method within tree- based motion planners. L4KDE utilises a neural network to predict the cost of transitioning between states under kinody- namic constraints, allowing for efficient retrieval of the cost when planning online. By leveraging the high representation capacity of neural networks, L4KDE is exceptionally novel in that it can also be directly conditioned on the parameters of the dynamics model (For example, velocity limits). By em- ploying the cost as a node selection heuristic in tree expansion of the underlying planning algorithm, we obtain significant improvements in planning performance over the commonly used Euclidean heuristic. We show that L4KDE consistently improves performance when used within a wide range of tree-based motion planning algorithms across a variety of tasks. Importantly we show that the improvement provided by L4KDE holds for state-of-the-art, tree-based, asymptotically optimal kinodynamic motion planners [1], [2]. II. R E L AT E D W O R K Kinodynamic planning refers to the class of robot systems that must obey kinematic and differential constraints [3]. For example, velocity, acceleration or force bounds in systems such as nonholonomic vehicles [4] and locomotion systems [5]. Sampling-based motion planners (SBPs) are a class of algorithms that avoid explicit representation of state space while connecting feasible states to form solution trajecto- ries. Compared to solutions given by trajectory optimisation techniques which are prone to local minima [6], or reac- tive methods which can be myopic [7], [8], SBPs provides probabilistic completeness [9] and almost-surely asymptotic optimality guarantee [10]. Tree-based methods such as RRT [11] are the predom- inant methods in SBPs. RRTs utilise random sampling to create Voronoi bias [12], which helps to explore the space 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) October 14-18, 2024. Abu Dhabi, UAE 979-8-3503-7769-9/24/$31.00 ©2024 IEEE 11788