Events Calendar

PhD Defense - Liron Cohen

Ph.D. Defense - Liron Cohen 6/17 10:00am "Efficient Bounded-Suboptimal Multi-Agent Path Finding and Motion Planning via Improvements to Focal Search"

Ph.D. Candidate: Liron Cohen
Date: Wednesday, June 17, 2020
Time: 10:00 AM - 12:00 PM
Committee: Sven Koenig (Chair), Bistra Dilkina, Peng Shi, Maxim Likhachev
Location: Online due to COVID-19
Zoom: https://usc.zoom.us/j/4421939378
Google Meet (only if there are issues with Zoom): meet.google.com/ova-uozj-vej

Title: Efficient Bounded-Suboptimal Multi-Agent Path Finding and Motion Planning via Improvements to Focal Search


Abstract:
Cooperative autonomous agents navigating in different environments can be useful in real-world application domains such as warehouse automation, search-and-rescue, fighting forest fires, traffic control, computer games and mining. Agents are required to navigate in such complex environments while avoiding obstacles and each other. In Artificial Intelligence (AI), a simplified model of this problem is called the Multi-Agent Path Finding (MAPF) problem. In MAPF, time is discretized into timesteps and the environment is discretized into cells that individual agents can occupy exclusively at any given timestep. Along with the environment, the MAPF problem also specifies unique start and goal cells for each agent. A solution to the MAPF problem is a set of paths, one for each agent, that take the agents from their respective start cells to their respective goal cells without collisions. A path for an agent is a sequence of move (between adjacent cells) or wait (at a cell) actions, each with some duration in timesteps.

Different measures for the cost of a solution to the MAPF problem, such as sum-of-costs or makespan, are commonly used in AI. Unfortunately, finding an optimal solution to a MAPF problem according to any of these cost measures is NP-hard, thus explaining why optimal MAPF solvers are inefficient in many real-world application domains. On the other end of the spectrum, suboptimal MAPF solvers are efficient but can be ineffective or even incomplete. One framework that balances the trade-off between efficiency and effectiveness is that of bounded-suboptimality. A bounded-suboptimal solver takes a user-specified constant w>=1 and returns a solution with a cost guaranteed to be at most w times the cost of an optimal solution. On the one hand, the freedom to explore suboptimal solutions allows these solvers to be more efficient than optimal ones. On the other hand, and as opposed to suboptimal solvers, these solvers ensure that their solutions are effective.

Unfortunately, state-of-the-art bounded-suboptimal MAPF solvers, all of which rely heavily on a bounded-suboptimal heuristic search method called Focal Search (FS), have a few shortcomings. First, small changes in w can significantly affect these solvers' runtime. Thus, it is often difficult to determine a w such that an effective solution is found efficiently. Second, these solvers are inefficient when agents are huddled together and the environment has some structural components that create bottlenecks. One such example is a typical warehouse domain. Here, the environment has long narrow corridors connecting open spaces or other corridors, and agents have to move between different regions of the warehouse through the corridors. Third, these solvers are inefficient when move actions have different durations. One such example is actions that model kinodynamically feasible motions. These shortcomings make bounded-suboptimal MAPF solvers inefficient in many real-world application domains, thus making suboptimal MAPF solvers the only viable option. This inefficiency is problematic because a low solution cost is often important for performing the task at hand sufficiently well.

In this dissertation, we improve FS in ways that resolve the above shortcomings of bounded-suboptimal MAPF solvers. Specifically, we develop an anytime framework for FS, which alleviates the need to choose w carefully. An anytime bounded-suboptimal MAPF solver based on this framework finds a ``good'' solution quickly and refines it to better and better solutions if time allows. We also show that FS provides bounded-suboptimality guarantees even when it is used with inflated heuristics. We develop an inflated heuristic, called the highway heuristic, which improves the efficiency of bounded-suboptimal MAPF solvers when the domain's environment has structural components that create bottlenecks. The highway heuristic alters the paths that agents choose by biasing the agents away from their individual optimal paths and towards paths on shared ``highways'' (directional lanes) in the environment. This results in implicit coordination of the agents, which, in turn, increases the efficiency of bounded-suboptimal MAPF solvers. Finally, we develop a version of FS that reasons about wait durations ``in bulk'' by using timeintervals instead of timesteps. A bounded-suboptimal MAPF solver that uses this version is efficient even when move actions have different durations, thus making it suitable for solving MAPF problems with actions that model kinodynamically feasible motions.

On the theoretical side, we formally prove that our improvements are bounded-suboptimal. On the experimental side, we show that our improvements result in increased efficiency in domains inspired by real-world applications. The overall impact of this dissertation is twofold. The first impact is in opening up the possibility of using bounded-suboptimal MAPF solvers for new application domains. New application domains include ones in which existing bounded-suboptimal MAPF solvers are not applicable, such as when the agents are kinodynamically constrained (for example, forklifts), as well as ones in which existing bounded-suboptimal MAPF solvers are too inefficient, such as automated warehouses. Different benefits of using bounded-suboptimal MAPF solvers in such application domains include safety (that is, the solutions are guaranteed to be collision-free), completeness and effectiveness (since the cost of the solution is guaranteed to be at most w times the cost of an optimal solution). The second impact is in revitalizing FS. Compared to other heuristic search methods, such as A* and wA*, FS is less restricted in the states it can choose to expand and can take advantage of a broader family of heuristics. Nevertheless, A* has received significantly more attention than FS from the scientific community.\footnote{According to Google Scholar, as of May 15, 2020, the first paper to introduce A* has been cited 9,522 times while the first paper to introduce FS has been cited 83 times.} Our improvements to FS make it more applicable and call for revisiting its importance.

WebCast Link: https://usc.zoom.us/j/4421939378

Audiences: Everyone Is Invited

Contact: Lizsl De Leon