Unified Safety-Critical Motion Planning for Connected Non-Holonomic Agents Using an Adaptive A* and Hybrid A* Integration

Abstract:

This paper presents a unified approach to safety-critical, multi-agent motion planning for connected autonomous robotic systems, seamlessly integrating the kinematic, dynamic, and safety constraints of individual agents, while reducing computational expense to ensure real-time applicability.

By integrating Voronoi Cells with an adaptive blend of A* and Hybrid A* algorithms, the proposed combinational planner ensures the generation of feasible and executable trajectories, guaranteeing efficient and collision-free navigation of multiple agents in dynamically complex environments. An additional deadlock avoidance strategy is proposed to further enhance the safety layer.

We demonstrate the effectiveness and robustness of our approach in terms of efficiency, collision avoidance, and deadlock resolution through simulations in diverse, randomly generated environments.
The results show that the proposed method outperforms existing methods in terms of dynamic considerations and obstacle avoidance, making it a practical real-time motion planning approach for connected non-holonomic agents in complex environments.

Key Contributions:

Voronoi Cell-Based Spatial Partitioning:

The environment is divided into Voronoi Cells, each assigned to a specific agent. This spatial partitioning ensures that agents maintain safe distances from each other and avoid collisions with obstacles. The Voronoi Cells are dynamically updated to adapt to the agents' movements and the environment's changing conditions

Combinational Planner:

The combinational planner dynamically switches between A* for long-range path planning and Hybrid A* for short-range, dynamically feasible paths.
A* is utilized to generate an efficient initial path, while Hybrid A* ensures that the path is executable given the agent's orientation and non-holonomic constraints. This dual approach optimizes both computational efficiency and path feasibility

Deadlock Resolution:

A novel deadlock resolution strategy allows an agent to temporarily exit its Voronoi Cell to avoid deadlock scenarios where two or more agents become stuck due to reciprocal constraints. The selected agent treats others as static obstacles while navigating out of the deadlock, effectively resolving the situation and ensuring smooth navigation.

Path Smoothing:

Once a path is generated, it undergoes Reed’s Shepp smoothing, which eliminates irregularities and sharp turns, ensuring that the path is smooth and feasible for real-world execution by non-holonomic agents.

Simulation and Results:

Extensive simulations were conducted to evaluate the performance of the proposed method in environments with varying obstacle densities and numbers of agents. The results demonstrate that the combinational planner significantly outperforms traditional methods like A* and Hybrid A* alone, particularly in terms of node exploration efficiency and time performance. The unified planner supported up to 30 agents in near real-time, showcasing its scalability and robustness in high-density scenarios

Simulations and paths for 8 agents in a simulated environment for the same start and end points for all agents using pygame

A* simulation

A* path

Hybrid A* simulation

Hybrid A* path

Combinational planner simulation

Combinational planner path

Please watch the video below to get detailed understanding of the research paper presented at the Ubiquitous Robots 2024 Conference in New York

Results :

The paper provides extensive simulation results to validate the proposed method. The simulations are conducted in environments with varying densities of obstacles and numbers of agents. The key findings are:

Efficiency: The combinational planner outperforms traditional methods like A* and Hybrid A* alone, particularly in complex environments with high obstacle density. It requires fewer nodes to find a solution, demonstrating superior efficiency.
Time Performance: The combinational planner is also faster, on average, than Hybrid A*, making it more suitable for real-time applications.
Safety: The integration of Voronoi Cells and the deadlock avoidance strategy ensures that there are no collisions between agents or with obstacles.
Scalability: The method scales well with the number of agents, maintaining performance even in scenarios with up to 30 agents.

The visual comparisons provided highlight the improved path quality and efficiency of the proposed method compared to baseline algorithms.

Applications :

The proposed method is applicable in a variety of real-world scenarios, including:

Autonomous Vehicles in Urban Environments: Managing traffic flow and preventing collisions in dense, dynamic urban settings.
Warehouse Robotics: Coordinating large numbers of robots in a warehouse, ensuring they can navigate around obstacles and each other without collisions.

Future Directions :

The paper concludes by suggesting future research directions:

Real-World Testing: Transitioning from simulation to physical hardware experiments to validate the method in real-world conditions, which introduces challenges like sensor noise and unpredictable disturbances.
Machine Learning Integration: Incorporating advanced machine learning techniques for better perception and handling uncertainty, which could further enhance the system’s robustness.
Human-Robot Collaboration: Developing protocols for human-robot interaction in multi-agent environments, particularly in shared spaces like warehouses or urban areas.