A lightweight and rapid bidirectional search algorithm

Path planning is a central component of robotic navigation, aiming to find a collision-free path from a start to a goal position while minimising distance, time, or energy. Conventional algorithms like A* and Dijkstra’s are widely used because of their reliability and optimality guarantees, but they often scale poorly in large or dense maps. Their computational costs rise sharply with environmental complexity, making them unsuitable for robots operating under real-time and hardware constraints. More modern approaches, like Bidirectional A*, Jump Point Search (JPS), and Shortest Path Faster Algorithm (SPFA), offer improved speed, adaptability, or flexibility. However, each faces trade-offs between computational cost, scalability, and real-time performance, posing ongoing challenges for robots operating in complex or resource-limited conditions.

The principle of the LiteRBS algorithm is to achieve fast and memory-efficient pathfinding by combining an aggressive bidirectional forward search with a reserve-queue fallback strategy. The algorithm improves upon the traditional bidirectional search by introducing dynamic frontier “attraction,” in which the search fronts from the start and goal continuously update their targets toward each other, allowing efficient convergence even when the most efficient merging point lies off-centre due to obstacles or map asymmetry. This adaptive merging drastically reduces node expansions, runtime, and memory use while maintaining completeness, both empirically and mathematically confirmed.

Extensive simulation experiments using around 100,000 randomly generated maps across various grid sizes (from 50×50 to 100×100) and obstacle densities ranging from 1% to 30% were conducted to evaluate its performance against grid-based competitors. These tests evaluated multiple metrics, including path length, computation time, expanded nodes, and peak memory consumption. Results revealed that LiteRBS consistently achieved statistically and practically significant performance improvements, such as cutting node expansion by more than 40%, speeding up runtime by up to 98%, and conserving memory overhead by as much as 96%. Its design is particularly suited for resource-limited robotic platforms, where both speed and efficiency are crucial for real-time operation. LiteRBS presents only a small trade-off in path optimality, with over 93% of all generated paths falling within the 10% suboptimality bound. The algorithm’s performance remained stable and density-invariant even under stress tests using very large grids (up to 1000×1000), confirming its robust scalability in computation time and memory preservation.

To validate its real-world validity, the team implemented LiteRBS on a Turtlebot3 Waffle mobile robot. In these tests, the robot navigated through partially observable environments and dynamically recalculated routes when new obstacles appeared. LiteRBS successfully recomputed viable paths in milliseconds, demonstrating its ability to function reliably under uncertainty and limited sensory input, which are key challenges in real-world robotics.

This paper was published in Robot Learning, ELSP Journal. Bah M, Giorgi I, Masala G. A lightweight and rapid bidirectional search algorithm. Robot Learn. 2025(2):0008

END