Abstract
Collision-free motion planning has been an active research area for more than twenty years and today effective solutions exist for many robotic systems: mainly some non-holonomic systems and some fully actuated systems. For these types of systems, a path can indeed be followed at different speeds giving rise to an infinite set of trajectories. Therefore, dynamic constraints can be decoupled from collision constraints: first a collision-free path is computed and then the dynamic constraints of the system are taken into account by the time-parameterization of the path.
The problem remains however open for dynamic systems that do not comply with the above property, even though a few preliminary solutions have been proposed for them. Some of these solutions are based on the optimal control approach, where a desired cost function is optimized. However, many such systems evolve in cluttered environments and there is a real need for computational methods which produce collision-free, admissible and optimal motions for these systems. As a few examples, we can think of humanoid robots, space robots or cars moving at high speed while avoiding obstacles. For these systems, dynamics has to be taken into account in the collision-free trajectory planning stage.
The aim of this workshop is to gather researchers working in collision-free motion planning with researchers working in control theory (optimal control/nonlinear optimization) for dynamic systems, in order to give a panorama of the state of the art and to discuss the issues related to combining motion planning algorithms with open-loop control techniques for complex dynamic systems.
Organizers
R. Lampariello | Dr. F. Lamiraux
|
Program
08:30 Welcome and Introduction – R. Lampariello and F. Lamiraux
Session I – Methods I
08:45 Prof. S. La Valle
Talk title: Obstacles to Computing Obstacle-Avoiding Trajectories
09:05 N. Chan, M. Zucker, Prof. J. Kuffner
Talk title: Towards Safe Motion Planning for Dynamic Systems Using Regions of Inevitable Collision
09:25 Prof. M. Diehl
Talk title: Fast Optimization Methods for Constrained Robot Control
09:45 Prof. S. Agrawal
Talk title: Differential Flatness Based Planning and Control of Classes of Mobile Vehicles
10:05 Coffee Break
Session II – Applications I
10:40 Dr. J.-P. Laumond and Dr. E. Yoshida
Talk title: Feedback experience in dynamic motion planning and control on the humanoid robot HRP-2
11:00 Dr. K. Mombaur
Talk title: Open-loop Stable Solutions of Optimal Control Problems for a Biped Running Robot
11:20 Dr. K. Harada
Talk title: Motion Planning for Whole Body Manipulation
11:40 Prof. Yamane and Prof. Nakamura
Talk title: Kinematics and Dynamics Algorithms for Humanoid Motion Planning
12:00 Lunch Break
Session III – Method II
14:30 L. Sentis
Talk title: Realtime Control of Humanoids
14:50 C. Reinl, Prof. O. von Stryk
Talk title: Trajectory planning for cooperating mobile robots using linearized mixed-integer optimal control
15:10 K. Bekris, A. Ladd, Prof. L. Kavraki
Talk title: Efficient Motion Planners for Systems with Complex Dynamics
15:30 Prof. E. Frazzoli
Talk title: Symbolic motion planning for highly-manoeuvrable robots
15:50 Coffee Break
Session IV – Applications II
16:20 Dr. F. Lamiraux
Talk title: Motion Planning for Realistic Dynamic Car Models
16:40 Dr. I. Belousov
Talk title: Motion planning for dynamic tasks: a study case in space robotics
17:00 Prof. Papadopoulos
Talk title: Path Planning with Collision Avoidance for Systems Exhibiting Nonholonomic Behavior
17:20 R. Lampariello
Talk title: Optimal motion planning for robots with dynamic constraints in grasping tasks
17:40 Final Round-Table Discussion
18:00 End Workshop
Workshop material
The Workshop material can be found on the Conference Workshops/Tutorials CD.
Full list of speakers with talk abstracts
1. Dr. J.-P. Laumond and Dr. E. Yoshida
LAAS-CNRS, Toulouse, France and Intelligent Systems Institute, AIST, Japan
www.laas.fr/~jpl/
Talk title: Feedback experience in dynamic motion planning and control on the humanoid robot HRP-2
Abstract:
We
will present a current research performed on dynamic motion planning
and control for humanoid robots. The first line of research is to study
the conditions of a possible decoupling between kinematics and dynamics
that gives rise to an iterative algorithm. Such a line will be
illustrated by tasks combining walking and manipulating in cluttered
environments. The second line of research is based on support polygon
reashaping. The method allows to extend the scope of the reachable
space while preserving the dynamic stability via ZMP-based control.
2. Dr. F. Lamiraux
LAAS-CNRS, Toulouse, France
www.laas.fr/~florent/
Talk title: Motion Planning for Realistic Dynamic Car Models
Abstract:
Dynamic
simulation is more and more replacing physical prototypes in car design
and manufacturing. There is a need to predict the dynamic behavior of
cars through standardized test using simulation models. Finding a
trajectory clearing a test using a dynamic model is in fact a
collision-free motion planning problem for dynamic systems with an
optimal control component since for some tests, the maximum clearing
speed needs to be computed.
In this talk, we will present an
original method for solving this problem based on trajectory
optimization. We will focus on the double lane change test, consisting
in changing lane to avoid a virtual obstacle and then to come back to
the first lane. Simulation results will show the effectiveness of the
method.
3. R. Lampariello
Institute of Robotics and Mechatronics, German Aerospace Center (DLR), Germany
www.robotic.dlr.de/Roberto.Lampariello/
Talk title: Optimal motion planning for robots with dynamic constraints in grasping tasks
Abstract:
Motion
planning problems related to space free-flying robots and fixed-base
redundant robots are first introduced, with particular attention to
grasping tasks. The methodological issue of on-line optimal motion
planning for redundant robots with geometric and dynamic constraints
then becomes relevant. The intrinsic coupling of the geometric path
with the dynamic constraints, poses interesting challenges and calls
for the development of efficient methods. Our current work on these
issues is presented, within the framework of the aforementioned
applications.
4. Dr. I. Belousov
HP Labs, Russia
Talk title: Motion planning for dynamic tasks: a study case in space robotics
Abstract:
We
will present a two-stage iterative algorithm, which provides
collision-free robot motion taking into account robot's dynamics. The
approach is based both on probabilistic methods for motion planning in
highly cluttered environments and on routines transforming a path into
a trajectory via the application of a dynamic simulator. We have
demonstrated the approach for the particular tasks of servicing the
satellite by a large space manipulator.
5. Prof. S. La Valle
Department of Computer Science, University of Illinois, USA
msl.cs.uiuc.edu/~lavalle/
Talk title: Obstacles to Computing Obstacle-Avoiding Trajectories
Abstract:
This
talk will survey some of the challenges of designing efficient
algorithms for computing open-loop trajectories for dynamical systems
subject to complicated obstacles. Issues covered will include
characterizing the region of inevitable collision, designing motion
primitives, and ensuring resolution completeness.
6. N. Chan, M. Zucker, Prof. J. Kuffner
Robotics Institute, Carnegie Mellon University, USA
www.ri.cmu.edu/people/kuffner_james.html
Talk title: Towards Safe Motion Planning for Dynamic Systems Using Regions of Inevitable Collision
Abstract:
The
conventional approach to replanning in dynamic environments typically
computes partial plans within the allotted CPU time and validates
explored states through robot-obstacle collision checks. However, this
approach cannot provide any safety guarantees for the robot beyond the
finite planning horizon. This talk will present our latest work
on the approximate computation of "regions of inevitable collision" for
state validation in a replanning framework for dynamic systems.
Experimental results that demonstrate the effectiveness of this
technique in providing dramatically improved safety for partial plans
in the domain of an underactuated dynamic vehicle will be shown.
7. Dr. Hirukawa
Intelligent Systems Institute, AIST, Japan
staff.aist.go.jp/hiro.hirukawa/
Talk title: Motion Pattern Generations under Unilateral Constraints
Abstract:
Legged robots travel in the environment by unilateral constraints,
which demands motion planning of the robots with the contact stability.
This talk introduces several kinds of the motion pattern generator
which can safisty the constraints.
8. Prof. S. Agrawal
Department of Mechanical Engineering, University of Delaware, USA
mechsys4.me.udel.edu/home/agrawal/Agrawal_CV.htm
Talk title: Differential Flatness Based Planning and Control of Classes of Mobile Vehicles
9. Prof. Yamane and Prof. Nakamura
Department of Mechano-Informatics, University of Tokyo, Japan
www.ynl.t.u-tokyo.ac.jp/~nakamura/index-e.html and 133.11.207.4/~katsu/
Talk title: Kinematics and Dynamics Algorithms for Humanoid Motion Planning
Abstract:
Humanoid
robotics has shown remarkable developments being supported by various
elemental technologies such as magnetic materials, electronic devices,
sensing components, structural materials and their manufacturing
technologies. The algorithms of kinematics and dynamics computation
have also become available and are supporting the humanoid robotics,
thanks to both their research advancement and that of processors and
networks. We will discuss the kinematics and dynamics algorithms used
for motion planning and simulations of humanoid robots.
10. L. Sentis
Artificial Intelligence Laboratory, Stanford University, USA
ai.stanford.edu/~lsentis/index.html
Talk title: Realtime Control of Humanoids
Abstract: In this talk I will describe a hierarchical control approach to
synthesize whole-body humanoid movements at runtime in the presence of
dynamic obstacles. I will also discuss the synthesis of complex movement
behaviors through combinations of low-level control primitives. Detection
of task feasibility, synthesis of human-like postures, and extensions of
the operational space framework for whole-body control, will be some
additional issues covered.
11. Prof. E. Frazzoli
Aero/Astro department, MIT, USA
Talk title: Symbolic motion planning for highly-maneuverable robots
Abstract:
In
this talk, I will present a symbolic approach to the solution of
collision-free motion planning problems for time-invariant dynamical
control systems with symmetries, such as mobile robots and autonomous
vehicles. The discussion of the theoretical framework will be
complemented with case studies and examples of application to a variety
of autonomous robots, including aerobatic aircraft and high-speed
off-road vehicles.
12. Dr. K. Harada
Visiting scholar Stanford University, Intelligent Systems Institute, AIST, Japan
Talk title: Motion Planning for Whole Body Manipulation
Abstract:
In this paper, we study the motion planning of a humanoid robot for
whole body manipulation tasks. We discuss the whole body manipulation
from both the experimental and the theoretical points of view.
First, we show several styles of manipulation tasks such as
pushing an object, climbing up a big gap with holding the handrail,
and lifting up a large object etc, and discuss the related theoretical
issues. We further discuss the motion planning method of the whole body
manipulation. Since this method uses the motion primitives, we first
show the method of generating the natural looking motion primitives.
Then, we show the motion planning method guided by the motion
primitives.
13. Dr. K. Mombaur
Interdisciplinary Center for Scientific Computing (IWR), University of Heidelberg, Germany
www.iwr.uni-heidelberg.de/~Katja.Mombaur//
Talk title: Open-loop Stable Solutions of Optimal Control Problems for a Biped Running Robot
Abstract:
We
generate optimal motions for a biped human-like robot configuration by
means of efficient optimal control techniques. The solutions can be
made open-loop stable by including stability conditions as constraints
in the optimal control problem. Used in the design phase of the robot,
this approach helps to determine optimal robot parameters with respect
to stability, as well as optimal trajectories and joint inputs.
14. Prof. M. Diehl
K.U. Leuven, Belgium
www.iwr.uni-heidelberg.de/~Moritz.Diehl/
Talk title: Fast Optimization Methods for Constrained Robot Control
Abstract:
We
present a state of the art method for solution of constrained optimal
control problems, the direct multiple shooting method, and apply it to
trajectory planning problems from industrial robots.
15. Prof. E. Papadopoulos
National Technical University of Athens
http://nereus.mech.ntua.gr/home.html
Talk title: Path Planning with Collision Avoidance for Systems Exhibiting Nonholonomic Behavior
Abstract:
In
this presentation we first describe a planning method for nonholonomic
mobile manipulator systems that includes an obstacle avoidance
capabilities and is very simple to compute. The method uses smooth
functions, such as polynomials. Next, this method is extended to
gymnast robots and space manipulator systems, i.e., dynamical systems
with integrals of motion.
16. Kostas Bekris, Andrew Ladd, Prof. Lydia
Kavraki
Dept. of Computer Science, Rice University
www.cs.rice.edu/CS/Robotics/
Talk tilte: Efficient Motion Planners for Systems with Complex Dynamics
Abstract:
In this talk, we will describe new motion planning techniques for the
solution of problems with complex dynamics. This work has been developed
in our laboratory over the last two years, The first planner
we will present is based on sampling-based motion planning and subdivision
methods. It avoids the use of metrics, which are difficult to define
for such systems, while achieving good coverage of the state space.
We have linked the planner with a physical simulator using the latter
as a black box, to generate realistic solution paths for automobiles.
The second approach is a greedy planner that uses low-dimensional
potential functions to greedily explore a tree towards the goal in
the high-dimensional state space. We have applied the planner to
tasks that require online replanning and show how the planner
guarantees collision-avoidance for a car like vehicle, while reducing the
computational cost of computing inevitable collision states through lazy
evaluation. Both planners, including the greedy approach, are probabilistically
complete through the use of a novel priority based scheme for the selection
of edges along the tree for expansion.
17. C. Reinl, Prof. O. von Stryk
Technical University Darmstadt
www.sim.informatik.tu-darmstadt.de
Talk title: Trajectory planning for cooperating mobile robots using linearized mixed-integer optimal control
Abstract:
To simultaneously optimize task allocation and trajectory planning for
multi-vehicle systems, this problem is modeled as a linearized
mixed-integer optimal control problem. This approach allows to regard
obstacles and collision avoidance constraints in our problem formulation.
Optimal paths can be computed with a tight coubpling of the vehicles
motions dynamic and the considered environment. As benchmark problem an
extension of the multi motorized traveling salesmen problem is
investigated.