Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed and can handle up to thousands of agents, they usually rely on the assumption that each action of the agent takes a time unit, and the actions of all agents are synchronized in a sense that the actions of agents start at the same discrete time step, which may limit their use in practice. Only a few algorithms were developed to address asynchronous actions, and they all lie on one end of the spectrum, focusing on finding optimal solutions with limited scalability. This paper develops new planners that lie on the other end of the spectrum, trading off solution quality for scalability, by finding an unbounded sub-optimal solution for many agents. Our method leverages both search methods (LSS) in handling asynchronous actions and rule-based planning methods (PIBT) for MAPF. We analyze the properties of our method and test it against several baselines with up to 1000 agents in various maps. Given a runtime limit, our method can handle an order of magnitude more agents than the baselines with about 25% longer makespan.

It is challenging to build socially-aware robots due to the inherent uncertainty in the dynamics of human behavior. To become socially-aware, robots need to be capable of recognizing activities in their environment to make informed actions in concert with co-present humans. In this paper, we present and validate an event-based method for robots to detect synchronous and asynchronous actions of humans when working as a team in a human-social environment. Our results suggest that our method is capable of detecting synchronous and asynchronous actions, which a step towards building socially aware robots.

Multi-agent path finding (MAPF) determines an ensemble of collision-free paths for multiple agents between their respective start and goal locations. Among the available MAPF planners for workspaces modeled as a graph, A*-based approaches have been widely investigated and have demonstrated their efficiency in numerous scenarios. However, almost all of these A*-based approaches assume that each agent executes an action concurrently in that all agents start and stop together. This article presents a natural generalization of MAPF with asynchronous actions where agents do not necessarily start and stop concurrently. The main contribution of the work is a proposed approach called Loosely Synchronized Search (LSS) that extends A*-based MAPF planners to handle asynchronous actions. We show LSS is complete and finds an optimal solution if one exists. We also combine LSS with other existing MAPF methods that aims to trade-off optimality for computational efficiency. Extensive numerical results are presented to corroborate the performance of the proposed approaches. Finally, we also verify the applicability of our method in the Robotarium, a remotely accessible swarm robotics research platform.

It is challenging to build socially-aware robots due to the inherent uncertainty in the dynamics of human behavior. To become socially-aware, robots need to be capable of recognizing activities in their environment to make informed actions in concert with co-present humans. In this paper, we present and validate an event-based method for robots to detect synchronous and asynchronous actions of humans when working as a team in a human-social environment. Our results suggest that our method is capable of detecting synchronous and asynchronous actions, which a step towards building socially aware robots.