A lightweight and rapid bidirectional search algorithm
School of Computing, University of Kent, Canterbury, UK
Abstract

Path planning in mobile robotics is critical for efficient navigation in complex environments. To date, grid-based planning remains a popular choice due to its simple spatial representation, integration with sensor data and the ability to encode motion constraints. This work contributes to this direction by proposing a novel and complete grid-based algorithm, LiteRBS (Lightweight and Rapid Bidirectional Search), optimised for computational efficiency and scalability. The algorithm balances aggressive bidirectional, forward search heuristics with a fallback strategy to reserve queues. Evaluated extensively against well-known algorithms like A*, bidirectional A*, Jump Point Search (JPS) and Shortest Path Faster Algorithm (SPFA), LiteRBS demonstrates statistically and practically significant reductions in memory usage (79%–96%), node expansion (40%–92%) and runtime (83%–98%), the latter remaining density-invariant across increasing spatial and environmental complexity. It handles non-central merges by dynamically adjusting search targets in each direction to “attract” nodes rapidly towards convergence. This yields flat search overhead as the problem scales to large and crowded maps. Real-world deployment on a Turtlebot3 robot demonstrates its responsiveness under partial observability and dynamic obstacle conditions. Overall, LiteRBS offers a scalable, lightweight and practical solution for the navigation of terrestrial robots in complex, resource-constrained environments.

Keywords

bidirectional search algorithm; grid-based search algorithm; LiteRBS; mobile robots; path-finding algorithm

Preview