Abstract
This paper presents an extension of Value Iteration Networks (VINs) designed to address the complex challenge of multi-robot coordination under non-holonomic constraints. By treating motion planning as a differentiable neural network task and interconnecting multiple networks through a mutual cost function, the authors enable agents to "negotiate" trajectories via gradient descent. This approach successfully resolves spatial conflicts in constrained environments, such as narrow corridors and bottlenecks, by optimizing global costs while respecting kinematic limits.
Introduction
Motion planning for a single robot is a foundational challenge in robotics, but the difficulty escalates significantly in multi-agent systems. Two primary hurdles complicate this task:
- Non-Holonomic Constraints: Most mobile robots, such as car-like vehicles, cannot move in any direction at any time. The inclusion of orientation as a critical state variable significantly increases the complexity of the underlying mathematics.
- The Curse of Dimensionality: In multi-robot systems, the search space for a valid solution grows exponentially with each additional agent. Traditional search-based algorithms often become computationally prohibitive for real-time applications.
The authors propose a middle ground: a method that is computationally efficient enough for real-time use while remaining sophisticated enough to handle car-like physics and cooperative behavior.
Methodology
The researchers build upon Value Iteration Networks (VINs), which embed a classic planning algorithm (Value Iteration) into a Convolutional Neural Network (CNN) architecture. To adapt VINs for multi-agent, non-holonomic scenarios, several key innovations were introduced:
Expanding the State Space
Standard VINs typically operate on 2D grids. This work expands the architecture to a 3D state space ($x, y, \theta$) to account for the robot's heading. Furthermore, iteration steps are mapped to time steps, effectively transforming a static path into a dynamic trajectory. To process this 3D space and the various actions available (e.g., moving straight or turning), the system utilizes 4D transition tensors within the CNN layers.
Interconnected VINs for Cooperation
Rather than employing a single monolithic network, each robot is assigned its own VIN. These networks are linked by a "mutual cost" function. When planned trajectories overlap, the system calculates a "collision punishment" using a Frobenius inner product across the agents' state distributions over time.
Optimization via Gradient Descent
Because the VIN architecture is differentiable, the system can use gradient descent to adjust the trajectories of all robots simultaneously. By employing a softmin operation during training instead of a hard argmin, the network produces smooth gradients. This allows robots to "feel" the proximity of potential collisions and adjust their plans proactively.
Experimental Setup and Results
The approach was evaluated using custom-designed simulated environments on a 15x5 grid with 8 discrete orientations. The simulations focused on specific coordination challenges:
- Turnaround Maneuvers: Car-like agents correctly performed circular maneuvers to reverse heading, respecting kinematic limits.
- Bottleneck Resolution: In narrow passages where only one robot could fit, the system coordinated the agents so that one waited while the other passed. The gradient descent naturally prioritized the agent closer to the bottleneck.
- Strategic Passing: In scenarios featuring a "passing place" (turnout), the network directed one robot to pull over specifically to allow an oncoming robot through, minimizing total system time.
Discussion and Future Work
A key insight of this work is that multi-agent cooperation can be framed as a standard optimization problem if the planner is differentiable. The system exhibits implicit priority, finding global solutions without hard-coded rules.
However, several limitations remain. The current model assumes centralized control, where a single system has access to all agents' states. In real-world decentralized scenarios, robots must predict others' behaviors without direct communication. Additionally, scaling the grid-based approach to massive urban environments and replacing deterministic transition filters with probabilistic ones to handle uncertain agents (like human drivers) are significant areas for future research.
Summary updated