
PhD Defense  Liron Cohen
Wed, Jun 17, 2020 @ 10:00 AM  12:00 PM
Thomas Lord Department of Computer Science
University Calendar
Ph.D. Defense  Liron Cohen 6/17 10:00am \"Efficient BoundedSuboptimal MultiAgent 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 COVID19
Zoom: https://usc.zoom.us/j/4421939378
Google Meet (only if there are issues with Zoom): meet.google.com/ovauozjvej
Title: Efficient BoundedSuboptimal MultiAgent Path Finding and Motion Planning via Improvements to Focal Search
Abstract:
Cooperative autonomous agents navigating in different environments can be useful in realworld application domains such as warehouse automation, searchandrescue, 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 MultiAgent 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 sumofcosts or makespan, are commonly used in AI. Unfortunately, finding an optimal solution to a MAPF problem according to any of these cost measures is NPhard, thus explaining why optimal MAPF solvers are inefficient in many realworld 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 tradeoff between efficiency and effectiveness is that of boundedsuboptimality. A boundedsuboptimal solver takes a userspecified 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, stateoftheart boundedsuboptimal MAPF solvers, all of which rely heavily on a boundedsuboptimal 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 boundedsuboptimal MAPF solvers inefficient in many realworld 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 boundedsuboptimal MAPF solvers. Specifically, we develop an anytime framework for FS, which alleviates the need to choose w carefully. An anytime boundedsuboptimal 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 boundedsuboptimality guarantees even when it is used with inflated heuristics. We develop an inflated heuristic, called the highway heuristic, which improves the efficiency of boundedsuboptimal 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 boundedsuboptimal MAPF solvers. Finally, we develop a version of FS that reasons about wait durations ``in bulk\'\' by using timeintervals instead of timesteps. A boundedsuboptimal 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 boundedsuboptimal. On the experimental side, we show that our improvements result in increased efficiency in domains inspired by realworld applications. The overall impact of this dissertation is twofold. The first impact is in opening up the possibility of using boundedsuboptimal MAPF solvers for new application domains. New application domains include ones in which existing boundedsuboptimal MAPF solvers are not applicable, such as when the agents are kinodynamically constrained (for example, forklifts), as well as ones in which existing boundedsuboptimal MAPF solvers are too inefficient, such as automated warehouses. Different benefits of using boundedsuboptimal MAPF solvers in such application domains include safety (that is, the solutions are guaranteed to be collisionfree), 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