This study examines a novel planning problem for multiple agents that cannot share holding resources, namedOffline Time-Independent Multiagent Path Planning (OTIMAPP). Given a graph and a set of start-goal pairs, the problem to be addressed is assigning a path to each agent, such that every agent eventually reaches its destination without blocking others, regardless of when each agent starts and finishes each own action. This motivation stems from timing uncertainties, including the reality gaps between planning and robot execution. In contrast to conventional solution, concepts of multirobot path planning that rely on timings, once OTIMAPP solutions are obtained, they can be executed without any synchronization between robot actions. Moreover, there is a theoretical guarantee that all robots eventually reach their destinations, provided they avoid interrobot collisions. This study attempts to establish OTIMAPP both theoretically and practically. Specifically, we present a formalization of the problem, solution conditions based on a categorization of deadlocks, computational complexities showing that OTIMAPP is computationally intractable, practical relaxation of the solution concept, two algorithms to solve OTIMAPP based on multiagent pathfinding algorithms, empirical results showing large OTIMAPP instances can be solved to some extent, as well as robot demonstrations of asynchronous OTIMAPP execution.

This paper studies a novel planning problem for multiple agents that cannot share holding resources, named OTIMAPP (Offline Time-Independent Multi-Agent Path Planning). Given a graph and a set of start-goal pairs, the problem consists in assigning a path to each agent such that every agent eventually reaches their goal without blocking each other, regardless of how the agents are being scheduled at runtime. The motivation stems from the nature of distributed environments that agents take actions fully asynchronous and have no knowledge about those exact timings of other actors. We present solution conditions, computational complexity, solvers, and robotic applications.

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.

Typical Multi-agent Path Finding (MAPF) solvers assume that agents move synchronously, thus neglecting the reality gap in timing assumptions, e.g., delays caused by an imperfect execution of asynchronous moves. So far, two policies enforce a robust execution of MAPF plans taken as input: either by forcing agents to synchronize or by executing plans while preserving temporal dependencies. This paper proposes an alternative approach, called time-independent planning, which is both online and distributed. We represent reality as a transition system that changes configurations according to atomic actions of agents, and use it to generate a time-independent schedule. Empirical results in a simulated environment with stochastic delays of agents' moves support the validity of our proposal.

This paper presents a novel robot-environment interaction in navigation tasks such that robots have neither a representation of their working space nor planning function, instead, an active environment takes charge of these aspects. This is realized by spatially deploying computing units, called cells, and making cells manage traffic in their respective physical region. Different from stigmegic approaches, cells interact with each other to manage environmental information and to construct instructions on how robots move.As a proof-of-concept, we present an architecture called AFADA and its prototype, consisting of modular cells and robots moving on the cells. The instructions from cells are based on a distributed routing algorithm and a reservation protocol. We demonstrate that AFADA enables a robot to move efficiently in a dynamic environment that stochastic changes its topology, comparing to self-navigation by a robot itself. This is followed by several demos, including multi-robot navigation, highlighting the power of offloading both representation and planning from robots to the environment. We expect that the concept of AFADA contributes to developing the infrastructure for multiple robots because it can engage online and lifelong planning and execution.

We study the iterative refinement of path planning for multiple robots, known as multi-agent pathfinding (MAPF). Given a graph, agents, their initial locations, and destinations, a solution of MAPF is a set of paths without collisions. Iterative refinement for MAPF is desirable for three reasons: 1) optimization is intractable, 2) sub-optimal solutions can be obtained instantly, and 3) it is anytime planning, desired in online scenarios where time for deliberation is limited. Despite the high demand, this is under-explored in MAPF because finding good neighborhoods has been unclear so far. Our proposal uses a sub-optimal MAPF solver to obtain an initial solution quickly, then iterates the two procedures: 1) select a subset of agents, 2) use an optimal MAPF solver to refine paths of selected agents while keeping other paths unchanged. Since the optimal solvers are used on small instances of the problem, this scheme yields efficient-enough solutions rapidly while providing high scalability. We also present reasonable candidates on how to select a subset of agents. Evaluations in various scenarios show that the proposal is promising; the convergence is fast, scalable, and with reasonable quality.

Cooperative intelligent transportation systems (ITS) are used by autonomous vehicles to communicate with surrounding autonomous vehicles and roadside units (RSU). Current C-ITS applications focus primarily on real-time information sharing, such as cooperative perception. In addition to realtime information sharing, self-driving cars need to coordinate their action plans to achieve higher safety and efficiency. For this reason, this study defines a vehicles future action plan/path and designs a cooperative path-planning model at intersections using future path sharing based on the future path information of multiple vehicles. The notion is that when the RSU detects a potential conflict of vehicle paths or an acceleration opportunity according to the shared future paths, it will generate a coordinated path update that adjusts the speeds of the vehicles. We implemented the proposed method using the open-source Autoware autonomous driving software and evaluated it with the LGSVL autonomous vehicle simulator. We conducted simulation experiments with two vehicles at a blind intersection scenario, finding that each car can travel safely and more efficiently by planning a path that reflects the action plans of all vehicles involved. The time consumed by introducing the RSU is 23.0 % and 28.1 % shorter than that of the stand-alone autonomous driving case at the intersection.

This paper presents a randomized self-stabilizing algorithm that elects a leader $r$ in a general $n$-node undirected graph and constructs a spanning tree $T$ rooted at $r$. The algorithm works under the synchronous message passing network model, assuming that the nodes know a linear upper bound on $n$ and that each edge has a unique ID known to both its endpoints (or, alternatively, assuming the $KT_{1}$ model). The highlight of this algorithm is its superior communication efficiency: It is guaranteed to send a total of $\tilde{O} (n)$ messages, each of constant size, till stabilization, while stabilizing in $\tilde{O} (n)$ rounds, in expectation and with high probability. After stabilization, the algorithm sends at most one constant size message per round while communicating only over the ($n - 1$) edges of $T$. In all these aspects, the communication overhead of the new algorithm is far smaller than that of the existing (mostly deterministic) self-stabilizing leader election algorithms. The algorithm is relatively simple and relies mostly on known modules that are common in the fault free leader election literature; these modules are enhanced in various subtle ways in order to assemble them into a communication efficient self-stabilizing algorithm.

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.