MAPF for complex robots

This project aims to address a critical gap in traditional techniques for solving Multi-Agent Path Finding (MAPF) problems. These methods typically rely on the simplifying assumption of holonomic robots, which limits their applicability to a narrower range of scenarios. We are motivated to address this limitation by developing a solution capable of accommodating robots with complex dynamics, thus expanding the scope of MAPF applications.

My project focuses on the development of a pipeline to address the challenge posed by various robot dynamics within MAPF scenarios. Unlike conventional approaches that rely on assumptions of robot holonomy, this pipeline leverages motion trees that inherently incorporate the dynamics of the robots. By doing so, we aim to provide a comprehensive solution capable of generating collision-free trajectories for multi-agent systems, irrespective of the complexity of their dynamics.

This approach introduces a significant change from conventional MAPF techniques by incorporating complexities of robot dynamics through motion trees. This departure allows us to overcome the limitations imposed by assumptions of holonomic robots. As such, This project represents a novel approach in the field of MAPF

To initiate our process, I first use the dynamics of each robot, conducting a series of forward rollouts. These rollouts serve as a representation of each robot’s reach at any given point. Beginning with the initial location of each robot as the starting node, I execute rollouts to identify nodes that remain clear of obstacles. These obstacle-free rollouts are then incorporated as nodes and edges in the respective robot’s graph. This iterative process is repeated for a designated number of iterations, culminating in the creation of graphs for each agent.

Subsequently, once the graphs are established, I proceed to convert each node into a hash map. In this mapping, the location of the node serves as the key, while the corresponding values comprise a list of nodes from other graphs that exhibit proximity to this particular node. This hashing process is executed for all nodes, extending to edges as well.

With these components in place, I can execute various MAPF algorithms. These algorithms leverage the mapped structures to conduct vertex and edge collision checks, thereby sidestepping potential collisions effectively. By integrating these meticulously crafted maps into our algorithms, I ensure a collision-free navigation process for multi-agent systems.