Navigating the unknown: A New Framework for Multi-Robot Motion Planning in Partially Mapped Environments

Imagine a team of autonomous robots exploring a disaster zone, searching for survivors in a building where the layout is completely unknown. Each robot must navigate around debris, avoid colliding with teammates, and dynamically adapt their paths as they discover new obstacles through their sensors. This scenario represents one of the most challenging problems in robotics: multi-robot motion planning in unknown environments.

The Challenge of Coordinated Robot Navigation

Multi-robot motion planning (MRMP) has traditionally focused on scenarios where the environment is fully known in advance. However, real-world applications often require robots to operate in partially mapped or completely unknown environments. This introduces a cascade of challenges:

• Dynamic replanning: As robots discover new obstacles through their sensors, they must frequently recalculate their paths
• Inter-robot collisions: Each robot must avoid not only static obstacles but also its teammates’ planned trajectories
• Complex dynamics: Real robots have physical constraints on their movement, including turning radius limits and velocity constraints
• Computational efficiency: The system must replan quickly enough to maintain smooth operation as new information arrives

Traditional approaches often struggle with these combined challenges, particularly as the number of robots increases or environments become more complex.

A New Adaptive Framework

Our research introduces a novel framework that addresses these challenges through two key innovations:

1. Two-Stage Adaptive Planning (MRAMP)

The framework employs a prioritized planning approach where robots are planned sequentially, but includes a crucial “collision-recheck” procedure. This solves a critical problem known as “collision-at-goal” - when a later-planned robot reaches its destination before an earlier-planned robot passes through that same location.

2. Guided Tree Growth

Rather than starting motion planning from scratch during each replanning cycle, the framework leverages previously computed trajectories to guide the growth of new motion trees. This significantly reduces computational overhead while preventing oscillatory behavior that can occur with frequent replanning.

Testing with Complex Robot Models

The framework was evaluated using two challenging robot models:

Snake-like robots: Modeled as articulated systems with a head and five connected links, each with its own dynamics. These robots must navigate while ensuring all body segments avoid obstacles - similar to how a multi-trailer truck must navigate tight spaces.

Car-like robots: Traditional wheeled vehicles with realistic turning radius constraints and velocity limitations.

Both models incorporate full dynamic constraints, making path planning significantly more complex than simple point-robot navigation.

Remarkable Performance Results

Testing across four different environment types - from maze-like structures to wave-pattern obstacles and concentric rings - the framework demonstrated exceptional performance:

• 90% success rate with 7 snake-like robots across most environments
• 90% success rate with 8 car-like robots in all test environments
• Significant improvements in both runtime and travel distances compared to baseline approaches

These results represent a substantial improvement over existing methods. Competitive baselines struggled to achieve even 25% success rates in the most challenging scenarios where our framework maintained 90% success.

Real-World Applications

This research has immediate applications in numerous domains:

• Search and rescue operations: Teams of robots exploring collapsed buildings or disaster zones
• Warehouse automation: Multiple robots navigating dynamic environments with moving inventory
• Space exploration: Rover teams exploring unknown planetary surfaces
• Environmental monitoring: Coordinated sensor networks in changing natural environments

The Path Forward

While the current framework shows strong performance, several areas present opportunities for future enhancement:

• Predictive planning: Incorporating trajectory prediction to anticipate robot movements and reduce collision-at-goal situations
• Learning integration: Using machine learning to improve decision-making about when to stick with existing paths versus exploring new routes
• Handling uncertainty: Extending the framework to deal with sensor noise, moving obstacles, and communication limitations between robots

Technical Innovation in Context

This work represents a significant step forward in making multi-robot systems practical for real-world deployment. By solving the fundamental challenges of coordination in unknown environments, it opens the door for more ambitious applications of robot teams.

The framework’s success stems from its holistic approach - rather than solving individual problems in isolation, it addresses the interconnected challenges of sensing, planning, coordination, and replanning as a unified system. This integration is crucial for robust performance in the unpredictable conditions that characterize real-world robotics applications.

The research demonstrates that with careful algorithm design and smart computational trade-offs, teams of robots can navigate complex unknown environments with remarkable reliability. As autonomous systems become more prevalent in our daily lives, frameworks like this will be essential for ensuring they can operate safely and effectively in the messy, unpredictable real world.

🚀 This research was conducted by Hoang-Dung Bui, Erion Plaku, and Gregory J. Stein, with support from the National Science Foundation. The full technical details and experimental results are available in the paper “Multi-Robot Guided Sampling-Based Motion Planning With Dynamics in Partially Mapped Environments” published in IEEE Access 2024 ( link ).