Titles and abstracts

Here you can find the titles and abstracts of all the talks presented at the workshop.

Note that a set of posters will also be presented during the workshop.

Robot Motion in the Real World: Challenges, Implications, and Prospects

Oliver Brock
Computer Science Department, University of Massachusetts, Amherst.

Based on the accomplishments of the motion planning community as a whole, it might be fair to say that today many theoretical aspects of motion planning are well understood. One of the great outstanding challenges for robot motion planning is to fully leverage this understanding in unstructured, uncertain, partially known, and dynamic environments. To generate robust motion in such environments, motion planners must represent uncertainty and reason about it. To reduce uncertainty, they must purposefully acquire sensory information to permit the successful completion of a task. As a consequence, the exploration process traditional motion planners perform in configuration space now has to take place in the real world and has to consider the limitations of actuation and sensing. In this talk, I will discuss the implications of these challenges and suggest some ideas to address them.

Enhancing Graph-Based and Cell-Based Motion Planning

Sven Koenig, joint work with K. Daniel, M. Likhachev, A. Nash and A. Ranganathan
Computer Science Department, University of Southern California (USC)

Motion-planning problems can be solved by discretizing the continuous configuration space with graph-based or cell-based techniques. Rapidly exploring random trees (RRTs) are an example of graph-based techniques, and the parti-game algorithm is an example of a cell-based technique. In this talk, we discuss the advantages and disadvantages of both approaches as well as ways of mitigating their disadvantages. In particular, we discuss how to use incremental heuristic search to speed up the parti-game algorithm, how to use any-angle planning to find short paths for cell-based planning, and how to use parti-game directed RRTs (PDRRTs) to combine graph-based and cell-based planning.

Applying Sampling-based Planners on Real Robots

Stefan Zickler, joint work with James Bruce, Mike Licitra, and Manuela Veloso
Computer Science Department, Carnegie Mellon University

In this talk I will describe some of the work we have done over the past several years to bring the advantages of modern randomized planners to real robot platforms. The applications have ranged from pure navigation tasks to multi-agent robot soccer teams. I will describe how we deal with unpredictable dynamic environments, and in particular the development of the ERRT path planner for such domains. I will also discuss how to manage the speed / quality tradeoff which is critical in applying motion planners on real robots with computation and execution time constraints. Finally, I will briefly cover examples of applications, including our two-time world champion RoboCup small-size soccer team.

Motion Planning for Anthropomorphic Systems

Jean-Paul Laumond

Anthropomorphic systems ask motion planning algorithms for special challenging issues. They are high dimensional mechanical systems with high redundancy with respect to the goal to be reached. On the other hand, digital actors applications demand not only to find a collision-free path but also to find a path capable to support eye-believable animations. Digital mannequins (used for ergonomics studies in PLM) as well as humanoid robots impose considering system dynamics to cope with motion stability issues. Via practical study cases, the talk overviews some recent results dealing with human motion imitation and understanding, dynamic motion planning and probabilistic diffusion control in high dimensional space search.

Sampling-based Partial Planning and Replanning for Dynamic Systems

James Kuffner
The Robotics Institute, Carnegie Mellon University

Safely Navigating Dynamic Environments

Thierry Fraichard
Inria Rhone-Alpes, currently visiting ETH

The primary purpose of this talk is to raise awareness in the Robotics community of the strong impact that the presence of moving objects in the environment of a robotic system has on its decision-making process when it comes to safe autonomous navigation. Two obvious (but often disregarded) facts are recalled first: (i) moving objects impose a strict upper-bound on the time available to the robotic system in order to determine its future course of action, and (ii) to guarantee motion safety, it is necessary to reason about the future behaviour of the moving objects. The Partial Motion Planning principle and the Inevitable Collision State concept are then called upon to deal with these two constraints. Partial Motion Planning (PMP) is an interruptible planning scheme: when the time available is over, it returns either a complete motion to the goal or a partial motion only, ie a motion that may not necessarily reach the goal. An Inevitable Collision States (ICS) for a robotic system is a state for which, no matter what the future trajectory of the system is, a collision eventually occurs. By combining both PMP and ICS, it is shown that it becomes possible to design autonomous navigation schemes that can operate safely in dynamic environments.

Real-Time Kinodynamic Planning: Physically-Realistic, Faster, Safer and Distributed

Kostas Bekris, joint work with Konstantinos Tsianos and Lydia Kavraki
Computer Science Department, Rice University

Robots in partially-observable, potentially dynamic environments require real-time planners to compute collision-free trajectories. We are working on such algorithms for systems with realistic motion constraints using sampling-based kinodynamic planning. The later paradigm easily accommodates a variety of systems and directly addresses both geometric and dynamic aspects of planning. However, as a search-based approach, it poses computational challenges when time limitations are imposed for real-time performance. This results in worse quality paths or partial paths that do not reach the goal. Moreover there are safety considerations, in terms of collision-avoidance, when a system has to respect dynamic constraints and operates under time limitations. In this talk, we highlight four characteristics of our work related to these problems. Firstly, we incorporate physical simulators in planning so as to be able to better represent realistic dynamics of the physical world, such as drift, friction, contacts and gravity. Secondly, we work on "informed" versions of sampling-based kinodynamic planners, where any available workspace information is utilized to reduce solution time, improve path quality and provide a high level guidance in the case of replanning. Thirdly, we propose a "continuous" replanning approach that guarantees the safety of a system with dynamics in tasks with static obstacles. Finally, we have extended this solution to a distributed algorithm for multiple communicating vehicles operating in the same environment. We show that through coordination multiple vehicles can also achieve in real-time collision avoidance while employing sampling-based kinodynamic planners.

Real-Time Motion Planning in Dynamic Environments and Crowd Simulation

Dinesh Manocha, joint work with Ming C. Lin, Russel Gayle, Jur van den Berg, Avneesh Sud and Erik Andersen: Team Gamma
Department of Computer Science, University of North Carolina

We will give an overview of our work on real-time motion planning in dynamic environments and its application to multi-agent and crowd simulation. Specifically, we present three new concepts and representations: multi-agent navigation graph that is computed using 2nd order Voronoi diagrams; reactive deforming roadmaps that use deformable links and physically-based retraction; and reciprocal velocity obstacles for multi-agent. These techniques can be used to generate physically-plausible and oscillation free motion of agents in complex, dense environments composed of hundreds of robots in real-time. We will also discuss their applications to multi-agent and crowd simulation in urban and indoor environments.

Roadmap-based Group Behaviors

Samuel Rodriguez, Robert Salazar, Troy McMahon, Burchan Bayazit, Jyh-Ming Lien, Nancy Amato
Department of Computer Science, Texas A&M University

Group behavior is very common in nature, and there have been ongoing research efforts to simulate such behavior in computer animations and robotics applications. Generally, such work considers behaviors that can be determined independently by each group member solely by observing its local environment. In this talk, we survey work by our group which investigates how integrating roadmap-based path planning techniques with flocking techniques can enable more sophisticated group behaviors. We extend ideas from cognitive modeling, and embed behavior rules in individual flock members and in the nodes and edges of the roadmap. We find that the global information provided by our rule-based roadmaps improves the behavior of autonomous characters, and in particular, enables more sophisticated group behaviors than are possible using traditional (local) flocking methods.

Real-time Adaptive Motion Planning and Extension to Collaborative High-DOF Robots

Jing Xiao, joint work with John Vannoy
Computer Science Department, UNC-Charlotte

This talk presents a general real-time adaptive motion planning (RAMP) approach for high-DOF robots, such as mobile manipulators, in dynamic environments with obstacles of unknown trajectories. The RAMP approach effectively deals with drastic and unknown changes in the environment through global planning of diverse trajectories. It facilitates real-time optimization of trajectories under various criteria, such as minimizing energy and time and maximizing manipulability. RAMP is readily extended to distributed, real-time planning for a team of mobile manipulators to collaborate spontaneously in the same environment with a common ttask objective, where two or more robots may also form subgroups of tight coordination to manipulate a common object together.

Beyond Motion: Multi-Robot "High-Level" Planning

Manuela Veloso
Computer Science Department, Carnegie Mellon University

In this talk, I will present some of the challenges of coordinating multiple robots to achieve specific objectives in highly dynamic environments. I will discuss the representation and execution of multi-robot plans when generated in a centralized and in a distributed manner. The work has been with my students within the context of robot soccer.

POMDPs for Manipulation

Tomas Lozano-Perez , joint work with Leslie Pack Kaelbling and Kaijen Hsiao
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology

Practical robot manipulation presents challenges in two key areas. One is the computational complexity arising from many degrees of freedom. The other is from uncertainty arising from imperfect sensing and modeling. While there has been dramatic progress on tackling planning with many degrees of freedom; progress in planning in the presence of uncertainty has been slower. This talk discusses some of our approaches to manipulation problems in the presence of uncertainty, building on the ideas from Markov decision processes, specifically approximate methods for solving partially observable Markov decision processes (POMDP). In particular, the focus will be on representational choices that need to be made to obtain tractable problems.

Stochastic Motion Roadmaps for Planning with Motion Uncertainty

Ron Alterovitz, joint work with Thierry Simeon and Ken Goldberg
Department of Electrical Engineering and Computer Sciences, UC Berkeley and UCSF Comprehensive Cancer Center

In many motion planning applications ranging from maneuvering vehicles over unfamiliar terrain to steering flexible medical needles through human tissue, the response of a robot to commanded actions cannot be precisely predicted. We present a new motion planning framework, the Stochastic Motion Roadmap (SMR), that explicitly considers uncertainty in robot motion to maximize the probability of avoiding collisions and successfully reaching a goal. In the framework, we first build a roadmap by sampling collision-free states in the configuration space and then locally sample motions at each state to estimate state transition probabilities for each possible action. Given a query, we use the roadmap to formulate a Markov Decision Process (MDP), which we solve using dynamic programming to compute stochastically optimal plans. The SMR thus combines a sampling-based roadmap representation of the configuration space, as in PRM's, with the well-established theory of MDP's. We present initial results for a non-homolonomic mobile robot with bang-bang steering and demonstrate that SMR's generate motion plans with significantly higher probabilities of success compared to traditional shortest-path plans.

Finding Nemo: Translating Reactive Tasks to Reactive Controllers

Hadas Kress-Gazit and George Pappas
Department of Electrical and Systems Engineering, University of Pennsylvania

Wouldn't it be nice if we could ask our robot to go find Nemo and transmit "I found him", and then have it do exactly that no matter where Nemo is? In this talk we will describe a framework in which a user specifies a complex task in structured English. This task is then automatically translated, using tools from the formal methods world, into a hybrid controller. This controller is guaranteed to control the robot such that its motion and actions satisfy the intended task, under some assumptions, in a variety of different environments. Furthermore, this framework can handle tasks involving multiple robots in a decentralized way.

Where Could They Be Hiding Now?

Jingjin Yu and Steve LaValle
Department of Computer Science, University of Illinois at Urbana-Champaign

Many important tasks involve reasoning about observations made while detectable bodies pass in and out of the field-of-view of sensors. Examples include counting people, surveillance, pursuit-evasion, target tracking, and analyzing team movements. We present general techniques and algorithms for reasoning about where moving bodies might have gone when outside of the sensor range. The main assumption is that the connected components of the shadow region can be maintained. Beyond this, the environment may be two or three dimensional, known or unknown, and simply or multiply connected. There may be one or more robots or humans carrying sensors. The sensor field-of-view may be limited by any depth or angle. The agents in the environment may be indistinguishable, distinguishable, or partially distinguishable (for example, there are several teams). The problem is formulated and solved in terms of simple information spaces that record minimal amounts of information relevant to solving various tasks. Shadow information spaces, integer linear programming, bipartite graphs, and maximum-flow algorithms are encountered along the way.

Poster Session

A small set of posters will also be presented during the breaks of the workshop:

  • Interpolated Graph Replanner
    by Roland Philippsen, Robotics and Artificial Intelligence Lab, Stanford University

    The E* algorithm is a path planner which supports dynamic replanning and path cost interpolation, resulting in lightweight repairing of plans and smooth paths during execution. Underlying E* is the interpretation of navigation functions as the crossing-time map of an expanding continuous surface whose propagation takes into account traversability.
    Unlike A* which constrains movements to graph edges, E* produces smooth trajectories by interpolating between edges. Like D* it supports dynamic replanning after local path cost changes. Similarly to Field-D* it uses interpolation to obtain smoothly varying values. However, E* interpolation is user-configurable, and it performs full tracking of the upwind dependency structure.
    An open-source implementation of the algorithm is available on Sourceforge along with several test programs and examples of integration into robotic systems.

  • A Probabilistic Algorithm for Model Based Motion Planning of Agile Air Vehicles in Complex Environments
    by Emre Koyuncu, N. Kemal Ure, Gokhan Inalhan,
    Controls and Avionics Laboratory, Istanbul Technical University, Istanbul, Turkey

    In this work, we consider the design of a probabilistic trajectory planner for a highly maneuverable air vehicle flying in a dense and complex city-like environment. Our design hinges on the decomposition of the problem into a) flight controls of fundamental agile-maneuvering flight modes and b) trajectory planning using these controlled flight modes from which almost any aggressive maneuver (or a combination of) can be created. This allows a significant decrease in control input space and search dimensions, thus presenting a natural way to design controllers and implement trajectory planning using the closed-form flight modes. Focusing on the trajectory planning part, we provide a three-step probabilistic trajectory planner. In the first step, the algorithm rapidly explores the environment through a randomized reachability tree search using an approximate line segment models. The resulting connecting path is converted into flight milestones through a line-of-sight segmentation. This path and the corresponding milestones are refined through a PRM implementation for creating dynamically feasible flight paths with distinct flight mode selections. We address the problematic issue of narrow passages through non-uniform distributed capture regions and conditions which prefer solutions that align the vehicle into entering the milestone regions in line with the next milestone to come. Numerical simulations in 3D and 2D demonstrate the ability of the method to provide real-time solutions in dense and complex environments.

  • Real-time motion planning for robots with stability and kinodynamic constraints
    by Konstantinos I. Tsianos and Lydia E. Kavraki,
    Physical and Biological Computing Group, Rice Univeristy

    Real robots have kinodynamic constraints in their motion, imposed by laws of physics and motor limitations. Planning for such robots can become challenging especially when the robot is only dynamically stable (e.g. segway). Moreover, in realistic scenarios, mobile robots need to operate in environments that are partially known, or contain moving obstacles. In this work a motion planning algorithm that deals with all those issues is presented. The algorithm samples random controls and uses forward integration in a physics simulator, to produce collision-free feasible motions. Furthermore, the planner operates in real-time, and revises the plan executed by the robot at regular time intervals. A subdivision scheme is used to efficiently explore the part of the space within the robots sensing range, and a low dimensional adaptive potential field is used to provide a general sense of direction towards the goal. Our experiments exhibit how an autonomous segway can navigate safely in static environments, going through narrow passages, without ever falling. Experiments in progress provide promising evidence that the same algorithm can be used in the presence of moving obstacles in the workspace.