Transcript CS790E - Computer Science & Engineering

Computer Science & Engineering, University of Nevada, Reno
CS790E Planning Algorithms
Lecture 1:
Applications
and Basic Ingredients of
Motion Planning
19 January 2010
Instructor: Kostas Bekris
CS790E
“Planning” Algorithms?
The term “planning” corresponds to multiple research challenges:
• e.g., scheduling tasks, path planning, action selection, etc.
We will focus on planning in an algorithmic way motions and actions for
•
“physical” systems, e.g., objects with geometry, mass and velocity, etc.
- This includes “real-world” systems such as:
✓ 3D rigid-bodies, robots and vehicles, machines in factory floors, molecules, etc.
- But also includes “virtual” agents such as:
• Robotics
✓ animated characters, simulated environments, etc.
• Artificial Intelligence
• Control
Theory
Many
different
fields are related to this challenge:
• Computer Graphics
• Computer Animation
• Scientific Simulation
• Computer Games
• Algorithms: Computational Geometry
• Computational Biology & Bioinformatics
• Virtual prototyping in manufacturing
• Architectural Design
CS790E
Planning Challenges in Various Fields
Artificial Intelligence
• Originally:
- Search & Automated Planning: How to search for a sequence of operations
that transform an initial problem state into a desired goal state
• Today:
- Decision-theory:
How to make optimal decisions or sequence of decisions
under the presence of uncertainty?
✓ imperfect state information, markov-decision processes (MDPs), game-theory
- Reinforcement learning:
Learn the right decisions or sequence of decisions
that must be executed for every possible state from experience.
In general:
• Machine planning is the complement to machine learning
- Once learning is being successfully performed, planning deals with the
decisions that have to be made
• AI focuses on discrete problems, we will mostly focus on continuous
CS790E
AI Examples
Discrete Puzzles, Operations and Scheduling
Rubic’s Cube
15-puzzle
Earth Observing 1 - NASA
Mars Rovers - NASA
Kasparov vs. Deep Blue - IBM
CS790E
Planning Challenges in Various Fields
Robotics
• Originally:
- Motion Planning:
How to move a rigid body without collisions
(i.e., a piano from one room to another without collisions)
• Today, new complications are being considered:
- Trajectory Planning:
How to compute feasible paths for robots/vehicles with
constrains in velocity and acceleration (systems with dynamics)
- Planning under Uncertainty: How to plan the motion of a moving system if
we are not absolutely certain about its location
- Motion Coordination:
How to move in coordination with other robots or in
the presence of other moving systems?
Many other problems are involved in building robots:
• state estimation, task allocation, mechanism design, dynamical system
modeling, feedback control, sensor design, computer vision, inverse
kinematics, humanoid robots, etc.
CS790E
Traditional Motion Planning
Piano Mover’s Problem - Gamma Group
Manocha & Lin - Univ. of N. Carolina, Chapel Hill
Benchmarks
Alpha Puzzle - James Kuffner - Carnegie Mellon Univ.
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
Kostas Bekris - Rice University
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
CS790E
Traditional Motion Planning
Jean-Claude Latombe - Stanford University
Manipulators
QuickTime™ and a
decompressor
are needed to see this picture.
Lydia Kavraki - Rice University
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
3 Manipulators moving a Piano - Juan
Cortes & Tierry Simeon - LAAS-CNRS France
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
CS790E
Traditional Motion Planning
Automotive Applications
Motion planning company:
• Kineo CAM
Customers:
• Renault
• Ford
• Airbus
• Optivus
Volvo cars plant
CS790E
From Traditional Planning to Planning with Dynamics
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
CS790E
From Traditional Planning to Planning with Dynamics
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
CS790E
From Traditional Planning to Planning with Dynamics
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
CS790E
Motion Planning with Dynamics & Under Uncertainty
Mobile Robots &
Vehicular Applications
CMU
DARPA Urban Challenge
Stanford
DARPA Urban Challenge
QuickTime™ and a
Compact Video decompressor
are needed to see this picture.
Honda - Japan
A robot pulling a trailer
Jean-Paul Laumond - LAAS - France
Jean-Paul Laumond - LAAS - France
QuickTime™ and a
GIF decompressor
are needed to see this picture.
PLEN Scating Robot - Japan
James Kuffner
CMU
CS790E
Planning Challenges in Various Fields
Control Theory
• Originally:
- Traditional Control: Optimal operation of continuous systems under
differential constraints (constrains expressed through differential equations)
✓ focusing on dynamics, stability, optimality, feedback (closed-loop control)
✓ ignoring obstacles
• Today:
- Open-loop non-linear control: Feasible open-loop trajectories for non-linear
syst.
In this course initially the focus will be on:
- open-loop trajectories instead of closed-loop
- feasibility as opposed to optimality
- rigid bodies without dynamics
Eventually, we will include: closed-loop problems, optimality and
dynamics
CS790E
Planning Challenges in Various Fields
Algorithms
• Combinatorics and complexity theory are important for planning
algorithms
• Important questions: are the algorithms complete?
• Most related sub-areas:
- Path finding in graphs
- Computational geometry
Computer Animation / Graphics / Simulation / Games
• Originally:
- Animated characters and agents moved in a cartoonish way
- As long as the agent reaches the goal that is enough
- Cool graphics more important than reasonable AI
• Today:
- Simulated Motion: It becomes increasingly important for simulated motion to
be physically realistic
- Game AI: Becomes the most important selling point for new games
- Industrial Simulation: Physics-based simulation is increasingly used before
real experiments are conducted - real products are produced - real factories
CS790E
Virtual Characters
James Kuffner - Carnegie Mellon University
Gamma Group
University of North Carolina, Chapel Hill
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
CS790E
Types of Problems
Other complications:
• sensor-based problems (i.e., partial-observability)
• uncertainty in sensing and acting
• multi-agent systems
• real-time requirements
Differential
Constraints &
Dynamics
3D
Constrained
Motion
Free
moving
2D
Discrete
Continuous
CS790E
Class Overview
Plan for CS790E (check schedule online:
http://www.cse.unr.edu/robotics/bekris/cs790_s10/event):
1. Applications and Basic Ingredients of Motion Planning
2. 2D Planning: Combinatorial Algorithms and Potential Functions
3. 3D Planning: The Configuration Space Abstraction
4. Sampling-based Motion Planning for Free-Flying Rigid Bodies
5. Extensions of Basic Motion Planning
6. Presentations I: Literature Survey and Project Proposal
7. Dynamics and Trajectory Planning
8. Planning for Cars and Trailers
9. Safety in Replanning with Dynamics
10. Feedback Planning & Planning for Hybrid Systems
11. Planning under Uncertainty
12. Presentations II: Experimental Results and Conclusions
CS790E
Basic Ingredients of Planning
State
• Planning problems involve a state space: all possible situations that
could arise
- e.g., position and orientation of a robot
- e.g., the locations of tiles in a puzzle
- e.g., the position, orientation, and velocity of a helicopter
• Typically, too large to represent and store explicitly
Time
• We have to make a sequence of decisions over a period of time
• Time can be modeled explicitly:
- e.g., driving a car as quickly as possible through an obstacle course (when
velocity is important, time is important)
• Time may be modeled implicitly:
- e.g., in solving the Rubik’s cube, actions just have to be executed in
succession
CS790E
Basic Ingredients of Planning
Actions
• A plan generates actions that manipulate/change the state.
- AI: actions and operators, Control theory and Robotics: inputs and controls
• How does the state change when actions are applied?
- Discrete time: State-valued function
- Continuous time: Ordinary differential equation
Initial and Goal States
• Start at an initial state and select actions so as to reach a goal state
Criterion
• Additional requirement the plan must satisfy:
- Feasibility: Find a plan that causes arrival at a goal state given the motion
capabilities of a system, regardless of its efficiency (already hard)
- Optimality: Find a feasible plan that optimizes performance in some carefully
specified manner, in addition to arriving in a goal state (even harder)
• Feasible solutions are preferable to having no solutions at all
CS790E
Basic Ingredients of Planning
Plan
• A plan may be:
- simply a sequence of actions to be taken
- a time-sequence of controls
- (uncertainty in action) an assignment of actions to all states (AI: policy,
Control theory: feedback control - feedback/reactive plan)
• Once a plan is available, there are three ways to use it:
1. Execution
-
Execute it either in simulation or on a physical device
2. Refinement
3. Hierarchical inclusion
CS790E
“Simpler” Planning: Planning in Discrete Spaces