Search-Based Robot Motion Planning With Distance-Based Adaptive Motion Primitives
Benjamin Kraljušić 1 , Zlatan Ajanović 2 , Nermin Čović 1 , Bakir Lačević 1 · 2025
Read Search-Based Robot Motion Planning With Distance-Based Adaptive Motion Primitives by Benjamin Kraljušić 1 , Zlatan Ajanović 2 , Nermin Čović 1 , Bakir Lačević 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01198.txt.
Introduction
Benjamin Kraljušić and co-authors speed up how robot arms plan their movements. Planners search a space of joint settings for a safe path, usually stepping with fixed-size moves that waste effort in open areas. Their method replaces those fixed steps with burs, bubbles of free space that grow as large as the surroundings allow. Open stretches are crossed in a few big steps, while tight spots still get fine care.
Built into an existing planning library, the approach was tried on arms with different numbers of joints in scenes of varied difficulty. It beat fixed-step planning clearly in complex scenes, above all for many-jointed arms, and matched it in simple ones.
Catalog record
| CREATOR | Benjamin Kraljušić 1 , Zlatan Ajanović 2 , Nermin Čović 1 , Bakir Lačević 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-01198
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Search-Based Robot Motion Planning With Distance-Based Adaptive Motion Primitives Benjamin Kraljušić 1 , Zlatan Ajanović 2 , Nermin Čović 1 , Bakir Lačević 1 Abstract This work proposes a motion planning algorithm for robotic manipulators that combines sampling-based and search-based planning methods. The core contribution of the proposed approach is the usage of burs of free configuration space ( 𝒞 \mathcal{C} -space) as adaptive motion primitives within the graph search algorithm. Due to their feature to adaptively expand in free 𝒞 \mathcal{C} -space, burs enable more efficient exploration of the configuration space compared to fixed-sized motion primitives, significantly reducing the time to find a valid path and the number of required expansions. The algorithm is implemented within the existing SMPL (Search-Based Motion Planning Library) library and evaluated through a series of different scenarios involving manipulators with varying number of degrees-of-freedom (DoF) and environment complexity. Results demonstrate that the bur-based approach outperforms fixed-primitive planning in complex scenarios, particularly for high DoF manipulators, while achieving comparable performance in simpler scenarios. I Introduction Sampling-based motion planning algorithms aim to avoid the explicit construction of \mathcal{C} -space [ 4 ] . The core idea of these algorithms is to generate a set of configurations by sampling the configuration space and attempting to locally connect them using collision-checking routines. This process yields a valid sequence of configurations – a path between the start and goal configurations of a robotic manipulator [ 5 ] . On the other hand, search-based motion planning algorithms treat the motion planning problem as a graph search problem. Due to the discrete nature of graphs, all search-based planning algorithms require a discrete representation of the \mathcal{C} -space either by sampling using motion primitives, state lattice or some other discretization method. Thus, the planning problem is reduced to constructing an appropriate graph representation of the configuration space and performing a search over this graph to connect the start with the goal configuration [ 17 ] . In this work, a motion planning algorithm is presented that performs heuristic graph search over a graph generated by sampling-based methods, with the aim of efficiently finding a solution that may be optimal or within a bounded level of suboptimality. Local paths within the graph are generated using burs of free configuration space – a planning structure proposed in [ 5 ] . Burs were chosen due to their proven exploration capabilities, as shown in the existing work. The ARA ∗ algorithm [ 21 ] was used as the search algorithm, as it quickly finds an initial solution and then efficiently improves it through an iterative process, relying on the results of previous searches. The main contribution of this paper represents developing an algorithm that carefully combines the advantages of both planning paradigms to efficiently find good paths. Fig. 1 : Expansion of different states using fixed motion primitives (left) and adaptive bur-based primitives (right) for scenario shown in the figure 2(b) . Pink-colored areas represent the \mathcal{C} -space obstacles. II Related Work Sampling-based planning algorithms are most commonly divided into two categories: Rapidly-Exploring Random Trees (RRT) [ 3 ] and Probabilistic Roadmaps (PRM) [ 9 ] . The PRM algorithm constructs a roadmap in the form of a graph, where nodes represent collision-free configurations of the robotic manipulator, and edges correspond to valid paths between those nodes. The initial and goal configurations are connected (if possible) to any two nodes in the roadmap, and a path between them is found via graph search [ 9 ] . On the other hand, RRT algorithm builds a tree from the initial configuration by incrementally connecting randomly sampled configurations using collision-checking routines. The algorithm terminates when the goal configuration is added to the tree. Many enhanced versions of these basic algorithms have been proposed. A more efficient variant of RRT is its bidirectional version, RRT-Connect [ 10 ] , which constructs two trees – one from the initial and the other from the goal configuration and attempts to connect them. Asymptotically optimal versions of these algorithms, RRT ∗ and PRM ∗ , have also been introduced [ 11 ] . Orthey et al. provide a comprehensive overview and comparative review of sampling-based motion planning algorithms [ 2 ] . One of the most notable graph search algorithms used for motion planning of robotic manipulators is A ∗ , developed in 1968 during the Shakey project [ 1 ] . The A ∗ algorithm, considered a generalization of Dijkstra’s shortest path algorithm [ 20 ] , uses a heuristic function to estimate the cost to the goal, thereby accelerating the search process. Although these algorithms are complete and find optimal solutions, their efficiency decreases significantly with increasing dimensionality of the search space. Higher dimensionality causes an exponential growth in the number of graph nodes (a so-called “curse of dimensionality”) [ 29 ] . Various variants of the A ∗ algorithm have been developed to improve performance under different planning scenarios. In general, performance, such as execution time and memory usage, can be improved by introducing weighting coefficients to the heuristic function, allowing for limited suboptimality of the solution [ 30 ] . The idea of the Weighted A ∗ algorithm was first introduced by Pohl [ 27 ] , who later proposed dynamic weighting coefficients [ 31 ] . Based on the observation that planning time is often limited in real-world problems, Likhachev et al. developed Anytime Repairing A ∗ (ARA ∗ ), which uses weighted heuristic search to quickly find a bounded-suboptimal solution and then refines it within the remaining time to reduce suboptimality [ 21 ] . Aine et al. showed that combining multiple heuristic functions can guide the search more effectively, resulting in faster discovery of acceptable-quality solutions [ 22 ] . An alternative approach is presented in [ 23 ] and [ 25 ] , where search acceleration is achieved using graphs of different resolutions. Pivtoraiko and Kelly introduced the concept of a state lattice. A state lattice is a graph representation of the configuration space where nodes represent configurations and edges correspond to feasible transitions between neighboring configurations [ 24 ] . These feasible transitions respect the system’s physical constraints. State lattices have proven to be a useful method for representing configuration spaces when searching for dynamically feasible trajectories [ 26 ] . Cohen et al. developed a motion planner that performs heuristic search over the configuration space and constructs a graph using motion primitives—minimal executable motions of the robotic manipulator [ 18 ] . This planner showed substantial performance in high-dimensional configuration spaces. In a subsequent paper, the authors extended the algorithm by introducing adaptive motion primitives and enabling planning in a lower-dimensional space when possible [ 19 ] . A different form of adaptive motion primitives, applicable to manipulators with single or dual robotic arms, is presented in [ 28 ] . Adaptive primitives for automated parking are presented in [ 35 ] . However, these primitives are rule-based and can not be generalized to different \mathcal{C} - spaces. Sotirchos and Ajanović provide a detailed comparison between sampling-based and search-based motion planning algorithms. In [ 17 ] , they compare the performance of the RRT-Connect and ARA ∗ algorithms as prominent representatives