Multi Agent Flocking and Navigation

Scenarios:

Scenario 1: Single Obstacle (0:00)
Scenario 2: A* vs UCS Runtime Comparison (0:37)
Scenario 3: Multiple Obstacles of Varying Size (1:14)
Scenario 4: Agents Begin Navigation in Local Minima (1:47)
Scenario 5: Single Narrow Pathway to Goal (2:22)
Scenario 6: Numerous Small Obstacles (2:47)
Scenario 7: First Node in Path Not in Line of Sight (Produces Odd Behavior) (3:28)
Scenario 8: Obstacle Next to Goal (Produces Odd Behavior) (3:46)

DOWNLOAD CODE AND EXECUTABLES

Simulation of multiple agents flocking together while navigating around obstacles toward a uniform goal
Probabilistic roadmap (PRM) used to generate the agent's possible paths
A* Search algorithm used to search possible paths (Runtime comparison with UCS across many trials at 0:50 - 1:14)
Boids flocking used for local agent interaction (see 3:40 - 3:45)
Force based local agent-collision avoidance (see 0:29 - 0:33 and 3:14 - 3:23)
Path smoothing - Agents travel to farthest visible node regardless of position (see 1:33 and 2:59)
Spherical agents animated to roll in the direction of movement. The rate of rotation is proportional to the velocity of movement and the size of the agents. (most visible in Scenario 2 at 0:37 - 0:51)
3D Rendered environment (Navigation is constrained to 2D)

The simulation assumes that all agents share the same goal
The simulation assumes that all agents start within a close proximity to each other. Thus, the first node in the path is the average position of the starting location of all agents. Scenario 7 produces odd behavior because obstacles are placed between the starting positions of the agents and the first node in the path. Although the agents are able to navigate to the goal, multiple collisions occur as the pathing expects the agents to pass through the line of obstacles.
The simulation assumes that agents prefer to flock around and circle the goal rather than slow down or stop. This can cause nearby obstacles to temporarily move agents away from the goal as seen in Scenario 8.

Getting the agents to roll around like a ball was tricky. I initially assumed rolling diagonally was as simple as rotating in the X and Y directions simultaneously, but this resulted in an unnatural wobbling movement. I spent a long time debugging and trying to figure out the math of how to make the ball rotate naturally. The solution I settled on simply involved rotating the ball toward the angle of movement, and then rotating the ball forward in proportion to the velocity. It's a somewhat hacky fix but the solution only appears unnatural when making sharp turns.

Google Sites

Report abuse