Abstract
In real-time multi-agent navigation, agents need to move towards their goal positions while adapting their paths to avoid potential collisions with other agents and static obstacles. Existing methods compute motions that are optimal locally but do not account for the motions of the other agents, producing inefficient global motions especially when many agents move in a crowded space. In my thesis work, each agent has only a limited sensing range and uses online action selection techniques to dynamically adapt its motion to the local conditions. Experimental results obtained in simulation under different conditions show that the agents reach their destinations faster and use motions that minimize their overall energy consumption. Real-time navigation of multiple agents in crowded environments has important applications in many domains such as swarm robotics, planning for evacuation, and traffic engineering. This problem is challenging because agents have conflicting constraints. On one hand, they need to reach their goals as soon as possible while avoiding collisions with each other and the static obstacles present in the environment. On the other hand, due to the presence of many agents and the real-time constraints, agents need to compute their motions quickly (every 0.1s), independently of each other and in a decentralized manner instead of planning in a joint configu-ration space. A recently introduced decentralized technique for realtime multi-agent navigation, the Optimal Reciprocal Collision Avoidance (ORCA) framework [van den Berg et al., 2011] guarantees collision-free motion for the agents. Although ORCA generates locally efficient motion for each agent, the overall behavior of the agents can be far from efficient; actions that are locally optimal for one agent are notnecessarily optimal for the entire group of agents. Consider, for example, the two groups of agents in Figure 1a that try to move past each other in a narrow hallway. The agents navigate using ORCA, which guarantees collision-free motion, but still end up getting stuck in congestion. In contrast, I seto develop navigation methods that encourage the agents to adapt their motions to their surroundings, for example, by accounting for their neighbors’ intended velocity during their