Swarm Path Planning

A decentralized navigation technique where each agent moves under the influence of an artificial potential field. This field generates:

• Attractive forces pulling the agent toward its goal.
• Repulsive forces pushing it away from obstacles and other agents.

The agent's motion is determined by the gradient (steepest descent) of the combined field. While computationally simple and reactive, naive implementations can lead to local minima where agents become trapped.

A geometric formalism for collision avoidance. For each agent, the algorithm identifies a set of velocity obstacles (VOs) in velocity space—velocities that would lead to a collision within a specified time horizon.

• The agent selects a new velocity outside this VO set.
• Reciprocal Velocity Obstacles (RVO) improves cooperation by assuming other agents will also take avoiding action, leading to smoother, more predictable trajectories. This approach is widely used in robotics and crowd simulation for its real-time, guaranteed collision-free properties.

A seminal rule-based model for simulating flocking, schooling, and herding behaviors. Each agent (a boid) makes steering decisions based only on its local neighbors, following three core rules:

• Separation: Steer to avoid crowding local flockmates.
• Alignment: Steer toward the average heading of local flockmates.
• Cohesion: Steer to move toward the average position of local flockmates.

Adding a fourth rule for obstacle avoidance adapts the model for path planning in cluttered environments, creating globally coherent group movement from purely local interactions.

Metaheuristics that use swarm principles to optimize paths for the entire group.

• Ant Colony Optimization (ACO): Simulates ants depositing pheromones. Agents probabilistically follow strong pheromone trails, reinforcing shorter paths. Ideal for discrete pathfinding on graphs (e.g., network routing).
• Particle Swarm Optimization (PSO): Treats each candidate path as a particle in a search space. Particles adjust their trajectory based on their own best-known solution and the swarm's global best, converging on an optimal or near-optimal collective path plan.

An advanced optimal control approach where each agent repeatedly solves a finite-horizon trajectory optimization problem. Key aspects:

• Each agent predicts its own future states and the likely behavior of neighboring agents.
• It optimizes its planned trajectory to minimize cost (e.g., energy, time) while avoiding predicted collisions.
• Plans are executed for a short interval, then the process repeats with updated sensor data. DMPC provides a formal framework for optimal, proactive planning but is computationally intensive.

A collaborative approach where the swarm collectively builds a map of an unknown environment while localizing itself within it. This is a foundational capability for path planning in unknown territories.

• Agents share local landmark observations and pose estimates.
• Using algorithms like a distributed Kalman filter or pose graph optimization, they fuse data to create a consistent global map.
• This shared spatial understanding enables efficient, coordinated exploration and terrain-aware path planning.

The Boid model is a foundational computational simulation of flocking behavior, defined by three simple, local steering rules for each agent: separation (avoid crowding neighbors), alignment (steer toward the average heading of neighbors), and cohesion (steer toward the average position of neighbors). It demonstrates how complex, fluid group motion can emerge from minimal, decentralized rules and is a direct precursor to many rule-based swarm path planning algorithms.

The Potential Field Method is a decentralized navigation technique where agents move under the influence of an artificial field of forces. In swarm contexts:

• Attractive potentials pull agents toward goals.
• Repulsive potentials push agents away from obstacles and other agents.
• Each agent calculates its own path by following the negative gradient of the combined field. This method provides smooth, collision-free trajectories but can suffer from local minima where agents become trapped.

The Velocity Obstacle (VO) paradigm is a real-time, decentralized collision avoidance algorithm. For each agent, it defines a set of velocities in velocity-space that would lead to a collision with another agent or obstacle within a specified time horizon. The agent then selects the closest collision-free velocity to its preferred velocity. Extensions like Reciprocal Velocity Obstacles (RVO) and Optimal Reciprocal Collision Avoidance (ORCA) improve cooperation by assuming other agents also employ similar reasoning, leading to more natural and oscillation-free paths.

Decentralized Control is the core architectural principle of swarm systems, where control and decision-making authority is distributed among all agents. For path planning, this means:

• No single agent has a global map or plan.
• Each agent makes navigation decisions based on local sensor data and limited communication with nearby neighbors.
• This architecture provides key advantages: scalability (performance doesn't degrade with swarm size), robustness (the system tolerates individual agent failures), and flexibility (the swarm can adapt to dynamic environments).

Emergent Behavior is the complex, system-level pattern that arises from the local interactions of simple agents following simple rules. In swarm path planning, the global behavior of coherent flocking, efficient obstacle avoidance, or dynamic lane formation is not explicitly programmed into any single agent. Instead, it emerges from the collective execution of local rules like those in the Boid model or Velocity Obstacle algorithms. This is a defining characteristic of swarm intelligence systems.

SwarmSLAM is a decentralized approach to Simultaneous Localization and Mapping. A group of agents collaboratively builds a consistent global map of an unknown environment while simultaneously determining their individual positions within it. This is critical for path planning in unmapped areas. Agents fuse their own sensor observations (e.g., LiDAR) with shared data from neighbors using algorithms like pose-graph optimization or Swarm Kalman Filters, creating a shared spatial understanding without a central mapping server.