Hybrid roadmap and bidirectional search trims robot path planning times

A hybrid algorithm that pairs probabilistic roadmaps with a bidirectional version of the A* search has produced shorter routes and faster planning times than conventional methods in a series of MATLAB/Simulink simulations, according to a study published in Discover Robotics. The work, led by Ravishankar Prakash Desai and colleagues, addresses a persistent bottleneck in autonomous robotics: finding collision-free paths quickly enough for robots that must operate in cluttered, changing environments such as warehouses, disaster zones, hospitals, and agricultural fields.

Classical path planners each carry well-known trade-offs. Dijkstra’s algorithm guarantees the shortest path by exhaustively exploring every option, but that thoroughness carries a heavy computational cost that makes it poorly suited to large-scale or real-time use. A* improves on this by adding a heuristic that steers the search toward promising regions of the state space, cutting the number of nodes examined while keeping paths near-optimal. Sampling-based methods such as the probabilistic roadmap, or PRM, tackle high-dimensional problems differently: they build a graph of collision-free configurations that supports rapid path queries across the free space. PRM alone, however, can return suboptimal paths and struggles to adapt when the environment changes rapidly.

The new framework combines these ideas in a specific way. First, PRM generates a sparse roadmap of the environment: it samples configurations at random, discards any that fall inside obstacles, and connects each surviving sample to its nearest neighbors, but only when the connecting edge lies entirely in collision-free space. The result is an undirected graph that captures the global connectivity of the workspace while representing only a small fraction of the full configuration space. Path planning then takes place on this reduced graph rather than on the entire map, which the authors note shrinks the effective search space dramatically, since the number of roadmap nodes is far smaller than the number of configurations in the full space.

The second ingredient is an enhanced bidirectional A* search that runs simultaneously from the start and the goal. Instead of expanding nodes outward from one origin, the algorithm grows two search frontiers until they intersect, then reconstructs the complete route by joining the forward and backward trajectories at the meeting node that minimizes the combined path cost. Under roughly balanced expansion, this halves the effective search depth compared with a unidirectional search. The implementation adds several refinements: priority-based node expansion that always grows the lowest-scoring node, early termination as soon as the frontiers cross, closed-set pruning to avoid re-expanding nodes, dynamic cost updating whenever a cheaper route to a node is found, and restriction of all expansion to roadmap neighbors rather than the full grid.

The framework also extends beyond single-robot, static-world planning. A priority-based coordination layer assigns each robot a priority derived from its distance to its target and its task urgency; higher-priority robots keep their planned trajectories while lower-priority robots replan around them. A space-time reservation strategy enforces a minimum separation between any two robots at every time step to prevent inter-robot collisions. For dynamic environments, an adaptive replanning routine monitors the scene continuously and triggers replanning when new obstacles intersect the planned trajectory, when existing obstacles invalidate part of the route, or when environmental changes break roadmap connectivity. The roadmap is then updated, invalid nodes and edges are removed, and the bidirectional search runs again on the refreshed graph.

Performance was quantified with five metrics: path length, computational time, path smoothness, success rate, and an adaptability factor defined as the product of the ratios of dynamic to static computation time and dynamic to static path length, where lower values indicate greater resilience. Simulations were run on a 30-by-30-unit map containing 15 non-overlapping obstacles, with PRM parameters of 1,000 sampled nodes, a connection radius of 3 units, and 10 nearest neighbors. The heuristic weight was set to 1.0 to preserve admissibility. Each experimental configuration was repeated across 30 independent trials with randomly generated start and goal positions to support statistical reliability.

The comparative results were consistent across scenarios. In a single-robot test from position {3,4} to {18,27}, the proposed method found a path of 56.5796 meters against 60.4394 meters for Dijkstra with PRM. In a four-robot multi-start, multi-goal scenario, the proposed framework shortened paths for three of the four robots and cut the cumulative distance from 251.2800 meters to 239.8885 meters, a 4.53 percent reduction. With eight robots, the total distance fell from 359.9363 meters to 346.7517 meters, a 3.66 percent improvement, with shorter routes for six of the eight robots. In sequential multi-goal tasks, the four-robot cumulative distance dropped 4.62 percent and the eight-robot total fell 4.50 percent, with individual gains of roughly 10.32 and 9.35 meters for two robots. Randomized task-ordering scenarios showed reductions of 4.60 percent for four robots and 3.99 percent for eight robots, with all robots benefiting in each case.

Computational gains were more striking. Running on a laptop with a 13th-generation Intel Core i7-13700H processor under MATLAB R2024b, the framework reduced execution time by roughly 18,000 seconds on average compared with the Dijkstra-PRM approach across the reported test cases, an advantage the authors attribute to the combination of roadmap-based search-space reduction, bidirectional exploration, priority-based expansion, and early termination. In a dedicated dynamic multi-robot comparison against two baselines, hybrid PRM with conventional A* and hybrid PRM with Dijkstra, the proposed method achieved an average planning time of 0.0043 seconds, versus 0.0128 seconds and 0.0150 seconds for the baselines, reductions of roughly 66 and 71 percent. It also posted the highest path efficiency at 78.09 percent, compared with 75.77 and 73.16 percent, and the shortest cumulative path length at 543.5 meters against 548 and 554 meters.

Not every measure separated the methods. All three algorithms in the dynamic comparison recorded the same 87.5 percent success rate, with seven of eight robots reaching their goals; robot R6 failed in all cases due to obstacle interactions and environmental constraints. Mission completion time was identical at 32.8 seconds, with 20 robot avoidance events and 90 obstacle avoidance events for each method, suggesting comparable safety and coordination behavior. Replanning counts differed only marginally: 9,143 events for the proposed method against 9,148 and 9,154 for the baselines, which the authors read as slightly more stable trajectories under moving obstacles rather than a decisive advantage.

The authors are explicit about the limits of the evidence. All results come from simulation in a relatively small environment with modest numbers of robots and obstacles, and the framework’s performance in extremely dense or large-scale settings remains untested. The roadmap abstraction is primarily suited to static conditions, since obstacle motion can invalidate precomputed connections and force costly roadmap updates; in the proposed design, PRM supplies the initial collision-free roadmap while the bidirectional search handles real-time adaptation. Future work, the team writes, will target deployment on physical robotic platforms, three-dimensional environments, large-scale heterogeneous multi-robot systems, and learning-based adaptive heuristics and energy-aware planning for highly uncertain settings. For now, the study offers a measured demonstration that combining roadmap abstraction with bidirectional heuristic search can yield consistent, if modest, gains in path quality alongside substantial reductions in planning time.

Subject of Research: A hybrid path-planning framework combining probabilistic roadmaps with an enhanced bidirectional A* search algorithm for autonomous robots in static, dynamic, and multi-robot environments

Article Title: Adaptive autonomous robot path planning using hybrid probabilistic roadmaps and bidirectional a star search

Article References: Desai, R. P., Suravarapu, A., Vardhan, S. V. J. V., Surampudi, S. S. L., & Potnuru, S. D. (2026). Adaptive autonomous robot path planning using hybrid probabilistic roadmaps and bidirectional a star search. Discover Robotics, 2(1), Article 30. https://doi.org/10.1007/s44430-026-00043-3

Image Credits: AI Generated

DOI: 10.1007/s44430-026-00043-3

Keywords: robot path planning, probabilistic roadmap, bidirectional A* search, multi-robot coordination, dynamic environments, adaptive replanning, MATLAB simulation, computational efficiency, obstacle avoidance, autonomous robots, heuristic search, collision-free paths