Description:FIELD OF THE INVENTION
This invention relates to autonomous robotics and path planning. More particularly, it concerns a bi-directional virtual search-based path planning system and method for autonomous robots navigating static and dynamic grid environments, enabling fast, optimal, and collision-free navigation through real-time dynamic replanning and multi-directional movement.
BACKGROUND OF THE INVENTION
Current autonomous robot navigation systems struggle with generating optimal paths in environments containing both static and dynamic obstacles. Traditional path planning algorithms either rely on single-directional search strategies or assume a static environment, limiting their ability to respond to changes in real-time. Additionally, many systems do not effectively handle computational efficiency and real-time decision-making, leading to sub-optimal performance in cluttered or dynamic spaces. This results in increased collision risk, longer navigation times, and higher energy consumption. A robust, real-time, and adaptive path planning mechanism is essential for safe and efficient autonomous robot movement across various structured and semi-structured environments.
US20250224727: An artificial intelligence (AI)-based system and method for autonomous navigation of robotic devices in dynamic human-centric environments are disclosed. The AI-based system comprises an object tracking subsystem, a probabilistic estimation subsystem, a socially compliant behavior subsystem, a constrained space navigation subsystem, a commands processing subsystem, a virtual cost-map layer subsystem, and a path-planning subsystem. The AI-based system obtains sensor data using sensors. The AI-based system employs artificial intelligence (AI) models and machine learning (ML) models for computing probabilistic position data and generating convex hulls. The AI-based system generates high-cost zones for identifying boundaries associated with groups to plan navigation paths. The AI-based system generates waypoints for the robotic devices based on detecting constrained spaces in the dynamic human-centric environments by analyzing the sensor data. The AI-based system extracts navigational insights based on processing natural language commands and adaptively selects the navigation paths for autonomous navigation of the robotic devices.
US20250172942: A method for operating a robot, including: capturing images of a workspace; capturing data indicative of movement of the robot; capturing LIDAR data as the robot moves within the workspace; generating a map of the workspace based on the LIDAR data; actuating the robot to drive; discriminating between an object on a floor surface along a path of the robot and the floor surface based on the captured images; actuating the robot to drive until determining all areas of the workspace are discovered and included in the map; and executing a cleaning function.
Current autonomous robot navigation systems using A*, D*, DWA, or RRT variants typically assume static environments or rely on single-directional search strategies, leading to longer path generation times and poor adaptability to changing conditions. Dynamic obstacle handling is limited or post-reactive, and computation-heavy approaches slow down real-time decision-making. These shortcomings cause increased collision risk, longer travel times, and greater energy consumption. The present invention solves these issues by introducing a bi-directional virtual search (BDVS) algorithm with integrated dynamic replanning, predictive collision avoidance, and multi-directional movement within a grid-based representation, producing faster, safer, and more efficient robot navigation.
SUMMARY OF THE INVENTION
This summary is provided to introduce a selection of concepts, in a simplified format, that are further described in the detailed description of the invention.
This summary is neither intended to identify key or essential inventive concepts of the invention and nor is it intended for determining the scope of the invention.
The invention provides a bi-directional virtual search-based path planning system for autonomous robots operating in grid environments containing static and dynamic obstacles. It initiates simultaneous forward and backward searches from robot and target positions, significantly reducing search iterations and improving path convergence.
A dynamic replanning mechanism integrates local feedback to update paths in real time upon detecting obstacle movement or invalidation. A predictive collision avoidance layer models direction-of-movement of dynamic obstacles for proactive rerouting.
Post-processing optimises the path for minimal travel steps and smooth movement. Eight-directional movement support allows diagonal navigation, reducing turns and travel time. This framework efficiently guides the robot through environment setup, search execution, optimisation, and dynamic replanning, achieving collision-free and energy-efficient navigation.
The system is modular and scalable, suitable for implementation on various platforms and grid sizes, and can be integrated into mobile robots, drones, or industrial AGVs.
To further clarify advantages and features of the present invention, a more particular description of the invention will be rendered by reference to specific embodiments thereof, which is illustrated in the appended drawings. It is appreciated that these drawings depict only typical embodiments of the invention and are therefore not to be considered limiting of its scope. The invention will be described and explained with additional specificity and detail with the accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
The illustrated embodiments of the subject matter will be understood by reference to the drawings, wherein like parts are designated by like numerals throughout. The following description is intended only by way of example, and simply illustrates certain selected embodiments of devices, systems, and methods that are consistent with the subject matter as claimed herein, wherein:
The proposed invention introduces a bi-directional virtual search (BDVS) algorithm designed to enhance the efficiency, safety, and adaptability of autonomous robot navigation in complex environments with static and dynamic obstacles. The system is implemented using a modular grid-based representation, allowing for flexible integration across simulation platforms like MATLAB.
FIGURE 1: SYSTEM ARCHITECTURE
The figures depict embodiments of the present subject matter for the purposes of illustration only. A person skilled in the art will easily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the disclosure described herein.
DETAILED DESCRIPTION OF THE INVENTION
The detailed description of various exemplary embodiments of the disclosure is described herein with reference to the accompanying drawings. It should be noted that the embodiments are described herein in such details as to clearly communicate the disclosure. However, the amount of details provided herein is not intended to limit the anticipated variations of embodiments; on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the scope of the present disclosure as defined by the appended claims.
It is also to be understood that various arrangements may be devised that, although not explicitly described or shown herein, embody the principles of the present disclosure. Moreover, all statements herein reciting principles, aspects, and embodiments of the present disclosure, as well as specific examples, are intended to encompass equivalents thereof.
The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of example embodiments. As used herein, the singular forms “a",” “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises,” “comprising,” “includes” and/or “including,” when used herein, specify the presence of stated features, integers, steps, operations, elements and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components and/or groups thereof.
It should also be noted that in some alternative implementations, the functions/acts noted may occur out of the order noted in the figures. For example, two figures shown in succession may, in fact, be executed concurrently or may sometimes be executed in the reverse order, depending upon the functionality/acts involved.
In addition, the descriptions of "first", "second", “third”, and the like in the present invention are used for the purpose of description only, and are not to be construed as indicating or implying their relative importance or implicitly indicating the number of technical features indicated. Thus, features defining "first" and "second" may include at least one of the features, either explicitly or implicitly.
Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which example embodiments belong. It will be further understood that terms, e.g., those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.
The proposed invention introduces a bi-directional virtual search (BDVS) algorithm designed to enhance the efficiency, safety, and adaptability of autonomous robot navigation in complex environments with static and dynamic obstacles. The system is implemented using a modular grid-based representation, allowing for flexible integration across simulation platforms like MATLAB.
The invention comprises an environment representation module where the workspace is modelled as a grid map containing static and dynamic obstacles.
An initialisation module sets robot and target positions, obstacle locations, and allowable movement directions.
A bi-directional virtual search engine launches simultaneous forward search from the robot’s current position and backward search from the target position. The two search frontiers meet to determine an optimal path faster than traditional single-directional searches.
A local feedback mechanism monitors obstacle movements and detects path invalidation. When changes occur, the system triggers a dynamic replanning routine without restarting the entire search process.
A predictive collision avoidance layer analyses the direction-of-movement of dynamic obstacles to anticipate future positions and adjust the path proactively.
An optimisation module post-processes the raw path to reduce unnecessary steps, smooth corners, and improve energy efficiency.
The system supports eight-directional movement within the grid (N, NE, E, SE, S, SW, W, NW), allowing more natural and flexible navigation with fewer turns.
A multi-layer path-planning architecture separates virtual search from executable path generation, enabling modular implementation and improved computational efficiency.
The algorithm uses a unit cell inflation logic to ensure safety margins around obstacles when generating paths.
A motion execution module translates the optimised path into control commands for the robot’s actuators, ensuring accurate following of the planned trajectory.
The system can be simulated or deployed on real robots. In simulation, grid sizes from 10×10 to 50×50 are supported, and static plus directional dynamic obstacles are modelled.
Code modules include functions such as bi-directional search, path optimisation, and local replanning, which can be integrated into robotics middleware or standalone software.
Security and safety protocols ensure that the robot stops or reroutes safely if an unpredictable obstacle suddenly appears.
The architecture is scalable and can be extended to three-dimensional grids or combined with sensor fusion for real-world perception.
This approach results in reduced search iterations, faster path generation, improved path optimality, and built-in real-time replanning capability compared to existing methods.
By combining forward and backward searches, predictive obstacle modelling, and post-processing, the invention provides an effective and efficient solution for autonomous navigation in complex environments.
BEST METHOD OF WORKING
The preferred embodiment deploys the bi-directional virtual search system on a mobile robot with onboard computing. The environment is represented as a grid map. The robot and target positions are initialised, and the BDVS engine starts simultaneous forward and backward searches. A local feedback mechanism monitors obstacle movements and triggers dynamic replanning when necessary. The optimisation module smooths the path before execution. The motion module converts the optimised path into robot control commands. This configuration achieves ~12–15% faster path generation with improved collision avoidance and path optimality compared to traditional algorithms.
The proposed system integrates a range of key features that collectively enhance autonomous robot navigation. It initiates simultaneous forward and backward virtual searches from both robot and target positions, reducing search time and improving path convergence compared to traditional uni-directional methods. A dynamic replanning mechanism, driven by a local search-based feedback loop, updates paths in real time when obstacles move or path invalidation occurs, enabling proactive and predictive re-routing. Post-processing optimises the generated path to minimise total travel steps and enhance smoothness, while support for eight-directional movement, including diagonal navigation such as NE or SW, increases flexibility and reduces turns. A collision avoidance layer models the direction of movement of dynamic obstacles to anticipate and avoid potential collisions. This framework efficiently guides the robot through a sequence of virtual and executable path-planning layers, from grid initialisation to target navigation, ensuring minimal collision risk and faster completion. It offers environment-independent scalability across compact and large-scale grids, with a forward–backward fusion model reducing search iterations by approximately 15% and multi-directional movement support within a discrete grid setting enhanced by unit cell inflation logic.
, Claims:1. A bi-directional virtual search-based path planning system for autonomous robots comprising:
an environment representation module configured to model a grid map with static and dynamic obstacles;
an initialisation module configured to set robot and target positions and movement parameters;
a bi-directional virtual search engine configured to perform simultaneous forward search from the robot and backward search from the target to generate an optimal path;
a local feedback mechanism configured to monitor obstacle movements and detect path invalidation;
a dynamic replanning module configured to update the path in real time upon detecting changes in the environment;
a predictive collision avoidance layer configured to model direction-of-movement of dynamic obstacles and adjust the path proactively;
an optimisation module configured to minimise travel steps and smooth the generated path;
a motion execution module configured to convert the optimised path into control commands for the robot; and
an output interface configured to present the planned path and status information to a user.
2. The system as claimed in claim 1, wherein the environment representation module supports multiple grid sizes and eight-directional movement for flexible navigation.
3. The system as claimed in claim 1, wherein the bi-directional virtual search engine reduces search iterations by combining forward and backward searches.
4. The system as claimed in claim 1, wherein the local feedback mechanism triggers dynamic replanning without restarting the entire search process.
5. The system as claimed in claim 1, wherein the predictive collision avoidance layer anticipates future positions of dynamic obstacles and reroutes proactively.
6. A method for bi-directional virtual search-based path planning for autonomous robots comprising:
modelling an environment as a grid map with static and dynamic obstacles;
initialising robot and target positions and movement parameters;
launching simultaneous forward search from the robot and backward search from the target to generate an optimal path;
monitoring obstacle movements and detecting path invalidation with a local feedback mechanism;
updating the path in real time upon detecting changes in the environment using a dynamic replanning module;
modelling direction-of-movement of dynamic obstacles and adjusting the path proactively using a predictive collision avoidance layer;
optimising the generated path to minimise travel steps and smooth corners; and
executing the optimised path on the robot by converting it into control commands.
7. The method as claimed in claim 6, wherein the environment model supports eight-directional movement for more flexible navigation.
8. The method as claimed in claim 6, wherein the bi-directional virtual search reduces search iterations compared to single-directional methods.
9. The method as claimed in claim 6, wherein the local feedback mechanism enables built-in real-time replanning capability.
10. The method as claimed in claim 6, wherein predictive collision avoidance anticipates dynamic obstacle movement to reduce collision risk.