Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to their goal locations without collisions. In this paper, we study the lifelong variant of MAPF, where agents are constantly engaged with new goal locations, such as in large-scale automated warehouses. We propose a new framework Rolling-Horizon Collision Resolution (RHCR) for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of the agents only within a bounded time horizon and ignores collisions beyond it. RHCR is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We empirically evaluate RHCR with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1,000 agents (= 38.9% of the empty cells on the map) for simulated warehouse instances, significantly outperforming existing work.

The feasibility of drifter studies in complex and tidally forced water networks has been greatly expanded by the introduction of motorized floating sensors. This paper presents a method for such motorized sensors to accomplish obstacle avoidance and path selection using the solutions to Hamilton-Jacobi-Bellman-Isaacs (HJBI) equations. The method is then validated experimentally.

Motorized floating sensors have distinct advantages over their non-actuated counterparts. A motorized unit can prevent the sensor from washing ashore or heading into dangerous areas, expanding the mission regions in which they can be feasibly operated. In this article, we present a control frame work and describe the physically realized system used to prove its effectiveness. The controller uses two minimum-time-to-reach (MTTR) functions-one giving the time to reach the center of the river and one giving the time to reach the shoreline. The MTTR functions are constructed from solutions to Hamilton Jacobi-Bellman-Isaacs (HJBI) Equations. Contours along these functions are used to define the state transition thresholds for an on-off controller. The first MTTR function is also used to construct the optimal bearing to travel back to the center of the river. We investigate the effectiveness of the controller using a software-in-the-loop (SIL) simulator. Using prototypes built at UC Berkeley, results from a field operational test in the Sacramento-San Joaquin River Delta are then presented to validate the simulation results.