Decentralized Multi-Agent Navigation Planning with Braids

Chris Mavrogiannis


Navigating a human environment is a hard task for a robot, due to the lack of formal rules guiding traffic, the lack of explicit communication among agents and the unpredictability of human behavior. Despite the great progress in robotic navigation over the past few decades, robots still fail to navigate multi-agent human environments seamlessly. Most existing approaches focus on the problem of collision avoidance without explicitly modeling agents’ interactions. This often results in non-smooth robot behaviors that tend to confuse humans, who in turn react unpredictably to the robot motion and further complicate the robot’s decision making.

In this talk, I will present a novel planning framework that aims at reducing the emergence of such undesired oscillatory behaviors by leveraging the power of implicit communication through motion. Inspired by the collaborative nature of human navigation, our approach explicitly incorporates the concept of cooperation in the decision making stage, by reasoning over joint strategies of avoidance instead of treating others as separate moving obstacles. These joint strategies correspond to the spatiotemporal topologies of agents’ trajectories and are modeled using the topological formalism of braids. The braid representation is the basis for the design of an inference mechanism that associates agents’ past trajectories with future collective behaviors in a given context. This mechanism is used as a means of “social understanding” that allows agents to select actions that express compliance with the emerging joint strategy by compromising efficiency. Incorporating such a mechanism in the planning stage results in a rapid uncertainty decrease regarding the emerging joint strategy that facilitates all agents’ decision making. Simulated examples of multi-agent scenarios highlight the benefit of reasoning about joint strategies and appear promising for application in real-world environments.