Necessary and sufficient conditions are described for stable distance-angle leader-follower formation control of first- and second-order holonomic and non-holonomic mobile robots. The distance-angle leader-follower formation is a problem of maintaining the desired relative distance and orientation of robots in a group. Our analysis shows that the input constraints on the leader are necessary for stable formation control. These constraints are summarized as follows: 1) In a team of first (second) order holonomic mobile robots, the leader has to be controlled as a first (second) order non-holonomic mobile robot; 2) In a team of first (second) order non-holonomic mobile robots, the control input of the leader must be limited so that the curvature is first (second) order differentiable. We further show that these constraints are sufficient for the followers to maintain formation. Moreover, we present globally asymptotically stable controllers and describe simulation experiments that demonstrate the effectiveness of these controllers.

In the Multi-Agent Path Finding (MAPF) problem, a set of agents moving on a graph must reach their own respective destinations without inter-agent collisions. In practical MAPF applications such as navigation in automated warehouses, where occasionally there are hundreds or more agents, MAPF must be solved iteratively online on a lifelong basis. Such scenarios rule out simple adaptations of offline compute-intensive optimal approaches; and scalable sub-optimal algorithms are hence appealing for such settings. Ideal algorithms are scalable, applicable to iterative scenarios, and output plausible solutions in predictable computation time. For the aforementioned purpose, this study presents Priority Inheritance with Backtracking (PIBT), a novel sub-optimal algorithm to solve MAPF iteratively. PIBT relies on an adaptive prioritization scheme to focus on the adjacent movements of multiple agents; hence it can be applied to several domains. We prove that, regardless of their number, all agents are guaranteed to reach their destination within finite time when the environment is a graph such that all pairs of adjacent nodes belong to a simple cycle (e.g., biconnected). Experimental results covering various scenarios, including a demonstration with real robots, reveal the benefits of the proposed method. Even with hundreds of agents, PIBT yields acceptable solutions almost immediately and can solve large instances that other established MAPF methods cannot. In addition, PIBT outperforms an existing approach on an iterative scenario of conveying packages in an automated warehouse in both runtime and solution quality.

In swarm control, many robots coordinate their actions in a distributed and decentralized way. We propose a consensus-based control barrier function (CCBF) for a swarm. CCBF restricts the states of the whole distributed system, not just those of the individual robots. The barrier function is approximated by a consensus filter. We prove that CCBF constrains the control inputs for holding the forward invariance of the safety set. Moreover, we applied CCBF to a practical problem and conducted an experiment with actual robots. The results showed that CCBF restricted the states of multiple robots to the safety set. To the best of our knowledge, this is the first CBF that can restrict the state of the whole distributed system with only local communication. CCBF has various applications such as monitoring with a swarm and maintaining the network between a swarm and a base station.

The Multi-agent Path Finding (MAPF) problem consists in all agents having to move to their own destinations while avoiding collisions. In practical applications to the problem, such as for navigation in an automated warehouse, MAPF must be solved iteratively. We present here a novel approach to iterative MAPF, that we call Priority Inheritance with Backtracking (PIBT). PIBT gives a unique priority to each agent every timestep, so that all movements are prioritized. Priority inheritance, which aims at dealing effectively with priority inversion in path adjustment within a small time window, can be applied iteratively and a backtracking protocol prevents agents from being stuck. We prove that, regardless of their number, all agents are guaranteed to reach their destination within finite time, when the environment is a graph such that all pairs of adjacent nodes belong to a simple cycle of length 3 or more (e.g., biconnected). Our implementation of PIBT can be fully decentralized without global communication. Experimental results over various scenarios confirm that PIBT is adequate both for finding paths in large environments with many agents, as well as for conveying packages in an automated warehouse.

Multipopulation games model interactions among many agents who have various roles. The imitative protocol describes when and how each agent changes her action in multipopulation games. Under existing imitative protocols, each agent imitates only agents who belong to the population that she belongs to. In other words, it is assumed that each agent knows the populations that the other agents belong to. However, the agents cannot always know the populations that the other agents belong to. In multipopulation games that consist of agents whose senses of values are different from one another, we consider situations where agents cannot know populations that the other agents belong to. We propose a population-independent imitative protocol, and derive the mean dynamics that is generated by the protocol.