Kavraki Lab

Key Facts

Table of Contents


09:00-09:10 Workshop Introduction (Neil, Swarat, and Lydia)
09:10-09:35 Speaker 1: Neil Dantam: Incremental Task and Motion Planning
09:35-10:00 Speaker 2: Esra Erdem: Hybrid Conditional Planning for Robotics
10:00-10:05 Poster Introductions -- Lydia Kavraki
10:05-11:10 Coffee Break / Poster Setup
11:10-11:35 Speaker 3: Kostas Bekris: Task Planning in the Presence of Many Objects
11:35-12:00 Speaker 4: Pieter Abbeel
12:00-01:30 Group Lunch and Discussion
01:30-02:15 Poster Presentations
02:15-02:40 Speaker 5: Michael Koval: Exploiting Domain Knowledge for Multi-Step Manipulation
02:40-03:05 Speaker 6: Kris Hauser: The nuances of hybrid structure in task and motion planning
03:05-04:00 Coffee Break and Poster Discussion
04:00-04:25 Speaker 7: Hadas Kress-Gazit: “don’t change your mind here”: correctness and feedback for physical robots performing high-level tasks
04:25-04:50 Speaker 8: Ken Butts (Industry Perspective): Applications of Path Planning Methods to Verification of Automotive Control Designs
04:50-05:30 Panel Discussion and Wrap up


Complex manipulation requires robots to identify not only the paths to reach objects, but also which objects to reach, in what order, and what style of action to perform. Such decisions combine the need for continuous, collision-free motion planning with the discrete actions of task planning. Efficient algorithms exist to solve these parts in isolation; however, integrating task and motion planning presents algorithmic challenges in generality, scalability, completeness.

Challenges in task and motion planning arise from the interaction of task and motion layers. Task actions affect motion planning feasibility, and motion plan feasibility dictates the ability to perform task actions. Current work on task and motion planning has achieved good performance by focusing on specific types of actions or solving expected-case scenarios, but achieving performant and complete solutions in general domains is a continuing challenge.


The goal of this workshop is to highlight recent applications and explore new methods for combining task and motion planning. We hope to identify new abstractions and algorithms for complex robot action. From this workshop, we expect participating researchers to identify and address important challenges, techniques, and benchmarks necessary for combining task and motion planning


This workshop is intended for researchers in robotics, AI planning, and motion planning who are interested in improving the autonomy of robots for complex tasks such as manipulation.

The two main target audiences for the workshop are: (1) members actively researching new methods, future trends and open questions in task and motion planning (2) people who are interested in learning about the current state-of-the-art in order to incorporate these methods into their own projects. We strongly encourage the participation of graduate students.


Neil Dantam

Title: Incremental Task and Motion Planning

Abstract: We present a new algorithm for task and motion planning (TMP) and discuss the requirements and abstractions necessary to obtain robust solutions for TMP in general. Our method is probabilistically-complete and offers improved performance and generality compared to a similar, state-of-the-art, probabilistically-complete planner. The key idea is to leverage incremental constraint solving to efficiently add and remove constraints on motion feasibility at the task level. We validate IDTMP on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared to the benchmark planner and a four-times self-comparison speedup from our extensions.

Bio: Neil Dantam is a postdoctoral research associate at Rice University working with Prof. Lydia Kavraki and Prof. Swarat Chaudhuri. Neil’s current research involves the use of Satisfiability Modulo Theories (SMT) solvers for Task and Motion Planning. Neil received a Ph.D. in Robotics from Georgia Tech, advised by Prof. Mike Stilman, and bachelors’ degrees in Computer Science and Mechanical Engineering from Purdue University. He has worked at iRobot Research, MIT Lincoln Laboratory, and Raytheon.

Esra Erdem

Title: Hybrid Conditional Planning for Robotics

Abstract: Conditional planning enables planning for sensing actions and their possible outcomes in addition to actuation actions, and allows for addressing uncertainties due to partial observability at the time of offline planning. Therefore, the plans (called conditional plans) computed by conditional planners can be viewed as trees of (deterministic) actuation actions and (nondeterministic) sensing actions. Hybrid conditional planning extends conditional planning further by integrating low-level feasibility checks into executability conditions of actuation actions in conditional plans. We introduce a novel hybrid conditional planning algorithm that incrementally constructs a hybrid conditional plan using parallel instances of a nonmonotonic hybrid planner. We show an application of hybrid conditional planning for robotics with a service robotics scenario where a mobile manipulator sets up a kitchen table, and evaluate our parallel planner over various mobile manipulation scenarios from the perspectives of computational efficiency and plan quality.

Bio: Esra Erdem is an associate professor of Computer Science and Engineering at Sabanci University. She received her Ph.D. at the University of Texas at Austin in 2002. Her research involves Artificial intelligence and in particular, the mathematical foundations of Knowledge Representation and Reasoning and Cognitive Robotics, and their applications.

Kostas Bekris

Title: Task Planning in the Presence of Many Objects

Abstract: This talk will discuss the design of effective rearrangement primitives for robot manipulators. Such primitives can be accessed by higher level task planners in order to more effectively interact with scenes that involve multiple objects. The discussed methods extend existing backtracking search approaches for solving monotone rearrangement problems to some non-monotone instances, where an object needs to be placed in an intermediate position before transferred to its final target. They also involve searching the space of object arrangements in a hierarchical manner. At a high-level a sampling-based primitive considers object arrangements as nodes in a graphical data structure, which can be connected via the use of monotone or non-monotone rearrangement primitives. The backtracking search is eventually replaced by an approximate but fast method of detecting an appropriate ordering of moving objects resulting in a computationally efficient but probabilistically complete way of solving rearrangement challenges.

Bio: Kostas Bekris is interested in designing algorithms for planning and coordinating the motion of robots and physically-realistic virtual agents. He received a Bachelor’s degree in Computer Science from the University of Crete in 2001. He then headed to Rice University in Houston, TX, where he completed both his Master’s (2004) and Doctoral (2008) degrees in Computer Science under the supervision of Prof. Lydia Kavraki. The title of his Ph.D. thesis was Informed Planning and Safe Distributed Replanning under Physical Constraints. On July 2008 he joined the Department of Computer Science and Engineering at the University of Nevada, Reno (UNR) as an Assistant Professor. On July 2012 he moved to Rutgers University and joined the Computer Science department as an Assistant Professor.

Pieter Abbeel

Pieter Abbeel received a BS/MS in Electrical Engineering from KU Leuven (Belgium) and received his Ph.D. degree in Computer Science from Stanford University in 2008. He joined the faculty at UC Berkeley in Fall 2008, with an appointment in the Department of Electrical Engineering and Computer Sciences. He has developed apprenticeship learning algorithms which have enabled advanced helicopter aerobatics, including maneuvers such as tic-tocs, chaos and auto-rotation, which only exceptional human pilots can perform. His group has also enabled the first end-to-end completion of reliably picking up a crumpled laundry article and folding it. His work has been featured in many popular press outlets, including BBC, New York Times, MIT Technology Review, Discovery Channel, SmartPlanet and Wired. His current research focuses on robotics and machine learning with a particular focus on challenges in personal robotics, surgical robotics and connectomics.

Michael Koval

Title: Exploiting Domain Knowledge for Multi-Step Manipulation

Abstract: Household manipulation presents a challenge to robots because it requires perceiving a variety of objects, planning multi-step motions, and recovering from failure. We present practical techniques that improve performance in these areas by exploiting domain knowledge. We empirically validate these techniques on HERB, a bimanual mobile manipulator, by performing a table clearing task that involves loading objects into a tray and transporting it. Preliminary results suggest that these techniques improve success rate and task completion time by incorporating expected real-world performance into the system design.

Bio: Michael Koval is a fourth year Ph.D. student in the Robotics Institute at Carnegie Mellon University, co-advised by Sidd Srinivasa and Nancy Pollard. His research focuses on developing robotic manipulation algorithms that are robust to clutter and uncertainty. In particular, he is interested in using real-time sensor feedback—such as that provided by tactile sensors—to make closed-loop manipulation primitives that are robust to uncertainty.

Kris Hauser

Title: The nuances of hybrid structure in task and motion planning

Kris Hauser is an Associate Professor at the Pratt School of Engineering at Duke University with a joint appointment in the Electrical and Computer Engineering Department and the Mechanical Engineering and Materials Science Department. He received his PhD in Computer Science from Stanford University in 2008, bachelor’s degrees in Computer Science and Mathematics from UC Berkeley in 2003, and worked as a postdoctoral fellow at UC Berkeley. He then joined the faculty at Indiana University from 2009-2014, where he started the Intelligent Motion Lab. He is a recipient of a Stanford Graduate Fellowship, Siebel Scholar Fellowship, and an NSF CAREER award.

Hadas Kress-Gazit

Title: “don’t change your mind here”: correctness and feedback for physical robots performing high-level tasks

Abstract: This talk will discuss how formal methods, both discrete and continuous, are used to automatically synthesize a controller from a reactive high-level specification for a robot with nonlinear dynamics. We show how we can (i) reason about and provide feedback regarding situations in which the robot may fail and (ii) synthesize the controllers that are guaranteed to produce correct robot behavior whenever possible.

Bio: Hadas Kress-Gazit is an Associate Professor at the Sibley School of Mechanical and Aerospace Engineering at Cornell University. She received her Ph.D. in Electrical and Systems Engineering from the University of Pennsylvania in 2008 and has been at Cornell since 2009. Her research focuses on formal methods for robotics and automation and more specifically on creating verifiable robot controllers for complex high-level tasks using logic, verification, synthesis, hybrid systems theory, and computational linguistics. She received an NSF CAREER award in 2010, a DARPA Young Faculty Award in 2012 and the Fiona Ip Li ‘78 and Donald Li ‘75 Excellence in teaching award in 2013.

Ken Butts

Title: Applications of Path Planning Methods to Verification of Automotive Control Designs

Abstract: Techniques for evaluating automotive embedded control system designs currently use a combination of automatic directed test generation and random testing to find undesirable behaviors. Existing techniques can fail to efficiently identify bugs because they do not adequately explore the space of system behaviors. This talk presents an approach that uses a technique originally developed for path planning applications, rapidly exploring random trees (RRT), to explore the state-space of embedded control designs. Given a Signal Temporal Logic (STL) requirement, the RRT algorithm uses two quantities to guide the search: The first is a robustness metric that quantifies the degree of satisfaction of the STL requirement by simulation traces. The second is a metric for measuring coverage for a dense state-space, known as the star discrepancy measure. The technique scales to industrial embedded control problems and is demonstrated on an automotive powertrain control system model.

Bio: Ken Butts received the B.E. degree in electrical engineering from General Motors Institute (now Kettering University), Flint, MI, the M.S. degree in electrical engineering from the University of Illinois, Urbana-Champaign, and the Ph.D. degree in electrical engineering systems from the University of Michigan, Ann Arbor. He is an Executive Engineer with the Powertrain and Chassis Division, Toyota Motor Engineering and Manufacturing North America, Ann Arbor, MI, where he is investigating methods to improve engine control development productivity


Instructions for Poster Presenters

Please bring to the workshop a printed, paper poster no larger that 40x60 inches. Easels and a backing poster board will be provided to hold your poster.