Navigation

The navigation subsystem takes in the current poses of the robots, and their assigned tasks, as well as a map of the environment, to generate a path from each robot to its task. The controller then computes velocities to track this trajectory. This subsystem ensures that all the agents are able to traverse around each other and navigate from their start positions to their goal locations without colliding with the environment, with one another, crowding, or slowing each other down.

Decentralized 2D A*

Using a decentralized 2D A* planner, we plan for each agent separately. This planner outputs a collision-free path for each robot only with respect to the occupancy grid map of the environment and does not guarantee robot-robot collision avoidance.

Lazy Traffic Controller

The local collision avoidance between robots is done by a centralized controller. The Lazy Traffic controller takes in the paths from the decentralized planner and is responsible for local robot-robot collision avoidance by calculating collision-free velocities for each robot. It consists mainly of two parts

• Velocity obstacles based velocity calculation
• Inter robot repulsion

Velocity Obstacles

For each agent, all other agents act as obstacles in the velocity space and hence invalidate a set of velocities that this agent can execute. Velocity obstacles tries to select the best velocity as close to the preferred velocity as possible from the set of valid velocities. Preferred velocity is calculated for each agent from the global A* path found by the planner. Staying on this A* path is the preferred thing to do unless otherwise ruled out due to obstacles.

Inter-Robot Repulsion

On top of velocity obstacles, inter-robot repulsion is added if there are any agents within the repulsion zone of the ego-agent. This is inversely proportional to the distance between 2 agents and helps to avoid collisions in tight spaces.