computational robotics

from tasks to motions

Path Planning in Dynamic Environments for Robotic Swarms

This work develops a path-planning approach to enable a swarm of robots move to a goal region while avoiding collisions with static and dynamic obstacles. To provide scalability and account for the complexity of the interactions in the swarm, the proposed approach combines probabilistic roadmaps with potential fields. The underlying idea is to provide the swarm with a series of intermediate goals which are obtained by constructing and searching a roadmap of likely collision-free guides. As the swarm moves from one intermediate goal to the next, it relies on potential fields to quickly react and avoid collisions with static and dynamic obstacles. Potential fields are also used to ensure that the swarm moves in cohesion. When the swarm deviates or is unable to reach the planned intermediate goals due to interference from the dynamic obstacles, the roadmap is searched again to provide alternative guides. Experiments conducted in simulation demonstrate the efficiency and scalability of the approach.

Approach

  • Combine roadmaps and potential fields to enable fast path planning for swarms in dynamic environments
  • Potential fields provide scalability
  • Probabilistic roadmaps provide high-level guidance for how the swarm should move towards the goal
  • Potential fields promote cohesion within the swarm
PSEUDOCODE
1. Construct a roadmap using PRM
2. Repeat until solved
3.     If members of the swarm have not moved significantly in some time, 
       re-weight the roadmap to account for the congestion
4.     Search the roadmap to compute intermediate goals
5.     Assign the next goal to robots that have reached their current goal
6.     Compute overall potential for each member of the swarm
7.     Compute new heading based on the overall potential
8.     Update positions

Global Path Planning via Probabilistic Roadmaps

  • Randomly distribute points in the environment
  • Discard points that collide with the static obstacles
  • Connect neighboring points with straight-line segments
  • Discard edges that collide with the static obstacles
  • Roadmap captures the connectivity of the free space
  • Use shortest path as guide from robot's position to goal

To bias the swarm away from cluttered areas, a weight is added to each edge indicating its minimum distance to an obstacle

Guiding the Swarm

  • To move the swarm towards the goal region, the swarm is provided with a global guide
  • The path is made up of the shortest path from the current robot position to the goal region
  • A* search is used to determine the shortest path

Global Replanning via Alternative Guides

  • If a robot gets stuck in a local minima or is obstructed by a dynamic obstacle, an alternative route is used
  • The weights on the roadmap are adjusted to account for the obstruction
  • The next few roadmap edges along the guide are penalized
  • A new guide is devised using the re-weighted roadmap

Local Path Planning via Potential Fields

  • each robot b is attracted to its next sub-goal along its guiding path
  • each robot b is strongly pushed away from obstacles
  • each robot b is weakly pushed away from its neighbors
  • each robot b is influenced by the heading of the robots that have been or are near its current position
  • the four potential fields are combined together

Related Publications

  • Wallar A and Plaku E (2014): “Path Planning for Swarms in Dynamic Environments by Combining Probabilistic Roadmaps and Potential Fields.” IEEE Symposium on Swarm Intelligence, pp. 290–297  [publisher]  [preprint]
  • Wallar A and Plaku E (2014): “Path Planning for Swarms by Combining Probabilistic Roadmaps and Potential Fields.” Springer LNCS Towards Autonomous Robotic Systems, vol. 8069, pp. 417–428  [publisher]  [preprint]