Events for June
-
Ph.D. Defense - Michael Tsang 6/11 2:00 pm
Thu, Jun 11, 2020 @ 02:00 PM - 04:00 PM
Thomas Lord Department of Computer Science
University Calendar
Ph.D. Defense - Michael Tsang 6/11 2:00 pm "Interpretable Machine Learning Models via Feature Interaction Discovery"
Ph.D. Candidate: Michael Tsang
Date: Thursday, June 11, 2020
Time: 2:00 PM - 4:00 PM
Committee: Yan Liu (Chair), Emily Putnam-Hornstein, Xiang Ren
Title: Interpretable Machine Learning Models via Feature Interaction Discovery
Abstract:
The impact of machine learning prediction models has created a growing need for us to understand why they make their predictions. The interpretation of these models is important to reveal their fundamental behavior, to obtain scientific insights into data, and to help us trust automatic predictions. In this dissertation, we examine how to explain black-box prediction models via feature interaction detection and attribution, i.e. if features influence each other and how these interactions contribute to predictions, respectively.
We first discuss how feature interaction detection leads to model interpretations of diverse domains such as image/text classification and automatic recommendation. Here, we focus on the special case of recommendation where interaction detection improves not only model interpretability but also prediction performance. We then discuss how to attribute predictions to feature interactions in a way that is simultaneously interpretable, model-agnostic, principled, and scalable. Our discussion culminates in the unification of interaction detection and attribution to yield general prediction visualizations that are both intuitive and insightful.
Meeting Links:
Zoom Meeting:
https://usc.zoom.us/j/5669704161
Meeting ID: 566 970 4161
Google Meet (ONLY A BACKUP - IF WE EXPERIENCE PROBLEMS WITH ZOOM):
https://meet.google.com/brt-fjya-ykd
Phone Number:
(US) +1 720-439-6997
PIN:455 863 061
WebCast Link: https://usc.zoom.us/j/5669704161
Audiences: Everyone Is Invited
Contact: Lizsl De Leon
-
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 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
-
PhD Defense - Max Pflueger
Wed, Jun 17, 2020 @ 04:00 PM - 05:30 PM
Thomas Lord Department of Computer Science
University Calendar
Ph.D. Defense - Max Pflueger 6/17 4:00 pm "Learning from Planners to Enable New Robot Capabilities"
Ph.D. Candidate: Max Pflueger
Date: Wednesday, June 17, 2020
Time: 4:00 pm - 5:30 pm
Committee: Gaurav S. Sukhatme (chair), Joseph Lim, Sandeep Gupta, Ali Agha
Title: Learning from Planners to EnableNew Robot Capabilities
Abstract:
Solving complex robotic problems often involves reasoning about behavior multiple steps in the future, yet many robot learning algorithms do not incorporate planning structures into their architecture. In this dissertation we show how we can harness the capabilities of planning algorithms to learn from the structure of the robotic problems we wish to solve, thus expanding beyond what was available from baseline planners. We consider problems in multi-arm manipulation planning, path planning for planetary rovers, and reinforcement learning for torque controlled robots, and show how in each case it is possible to learn from the behavior of planning algorithms that are limited and unable to solve the full generalized problem. Despite not being full solutions these planners provide useful tools and insights that can be leveraged in larger solutions.
In multi-step planning for manipulation we develop a high level planner that can find solutions in difficult spaces by solving sub-problems in sub-spaces of the main planning space. For planetary rovers show how to use inverse reinforcement learning to learn a new planning algorithm that can function on different (and generally cheaper) input data. Reinforcement learning algorithms often suffer from unstable or unreliable training, we show how this can be mitigated by augmenting the robot state with a state embedding space learned from planner demonstrations.
Planning and control algorithms often rely on rigid and prescribed assumptions about the nature of robot problems, which may not be suitable for the generalized and versatile robot systems we wish to build. However, as this dissertation argues, those structures are still useful in informing the behavior of more flexible families of algorithms.
Meeting Links:
Zoom Meeting:
https://usc.zoom.us/j/93816840971
Meeting ID: 938 1684 0971
Google Meet (ONLY A BACKUP - IF WE EXPERIENCE PROBLEMS WITH ZOOM):
Meeting ID:
https://meet.google.com/iuj-gygb-utw
WebCast Link: https://usc.zoom.us/j/93816840971
Audiences: Everyone Is Invited
Contact: Lizsl De Leon
