Just a Click

Sunday, August 23, 2009

Robotics Planning


Definitions

robot
task planner
guarded motion
A motion of the form move along path until sensory-condition.
compliant motion
A motion of the form move along direction d with force = 0 perpendicularly to d. More intuitively, moving along a surface while maintaining a fixed pressure, such as when scraping paint off of a window with a razor.
effector
actuator
A device that converts software commands into physical motion, typically electric motors or hydraulic or pneumatic cylinders.
degree of freedom
sensors
sonar
Sensing system that works by measuring the time of flight of a sound pulse to be generated, reach an object, and be reflected back to the sensor. Wide angle but reasonably accurate in depth (the wide angle is the disadvantage).
infrared
Very accurate angular resolution system but terrible in depth measurement.
recognizable set
landmark
An easily recognizable, unique element of the environment that the robot can use to get its bearings.

Motivations

  • continuous -- states and actions are drawn from a continuum of physical configurations and motions
  • low cost

Task Planning

Task planning is divided into three phases: modeling, task specification, and manipulator program synthesis.
There are three approaches to specifying the model state:
  1. Using a CAD system to draw the positions of the objects in the desired configuration.
  2. Using symbolic spatial relationships between object features (such as (face1 against face2). This is the most common method, but must be converted into numerical form to be used.
One problem is that these configurations may overconstrain the state. Symmetry is an example; it does not matter what the orientation of a peg in a hole is. The final state may also not completely specify the operation; for example, it may not say how hard to tighten a bolt.

Motion Planning

Motion Planning Definitions

basic motion planning problem
configuration of object A
A specification of the position of every point in the object, relative to a fixed frame of reference. To specify the configuration of a rigid object A, it is enough to specify the position and orientation of the frame FA with respect toFW. The subset of W occupied by A at configuration q is denoted by A(q).
configuration space of object A
dimension of C
The dimension of a configuration space is the number of independent parameters required to represent it as Rm. This is 3 for 2-D, and 6 for 3-D.
chart
A representation of a local portion of the configuration space. C can be decomposed into a finite union of slightly overlapping patches called charts, each represented as a copy of Rm.
Distance between configurations
Path
free-flying object
C-obstacle
C-obstacle region
Free space
kinematics
dynamics
Motions of material bodies under the action of forces.
force-compliant motion
Rotary motion
Rotation around a fixed hub.
prismatic motion
Linear movement, as with a piston in a cylinder.

Skeletonization (Roadmap) Methods

To be complete for motion planning, skeletonization methods must satisfy two properties:
The kinds of skeletonizations are visibility graphs, Voronoi diagrams and roadmaps, which consist of silhouette curves andlinking curves. (This formulation due to Russell and Norvig; note that Latombe calls all of these things "roadmap methods.")

Visibility Graphs

Voronoi diagram

A roadmap method based on retraction. A continuous function of Cfree is defined onto a one-dimensional subset of itself. The Voronoi diagram consists of those curves in the space that are equidistant from two or more obstacles; these curves form the skeleton.

Cell Decomposition

A global approach to motion planning. The intuitive idea is to break the space down into a finite number of discrete chunks.

Potential Fields

Potential fields are very efficient but suffer from local minima. Two approaches overcome this:
  • design potential functions with no local minima other than the goal configuration
  • complement the basic potential field approach with mechanisms to escape from local minima

Landmark-Based Navigation

Configuration Space

Generalized Configuration Space

The term generalized configuration space is used to describe systems in which other objects are included as part of the configuration. These may be movable, and their shapes may vary.
  1. Partition the generalized configuration space into finitely many states. The planning problem then becomes a logical one, like the blocks world. No general method for partitioning space has yet been found.
  2. Restrict object motions to simplify planning.

Extensions of the Basic Problem

Multiple Moving Objects

The second and third extensions yield configuration spaces of arbitrarily large dimensions. Planning can be done in acomposite configuration space which is the cross-product of the individual configuration spaces (this is called centralized planning), or another method called decoupled planning can be used to plan the motions more or less independently and interactions are only considered in the second phase of planning.

Kinematic Constraints

holonomic constraints
nonholonomic constraints

Uncertainty

Grasp Planning

There are three principal considerations in gripping an object. They are:
  • stability -- the grasp should be stable in the presence of forces exerted on the grasped object during transfer and parts-mating motions

Computational Complexity

These theorems are taken from Latombe's book (see Sources).
Theorem 2 (Joints) In the absence of obstacles, deciding whether a planar linkage in some initial configuration can be moved so that a certain joint reaches a given point in the plane is PSPACE-hard.
Theorem 6 (Velocity-bounding) Planning the motion of a rigid object translating without rotation in three dimensions among arbitrarily many moving obstacles that may both translate and rotate is a PSPACE-hard problem if the velocity modulus of the object is bounded, and an NP-hard problem otherwise.

Reducing Complexity

It is possible to approximate the real problem before giving it to the motion planner; it is reasonable to trade generality for improved time performance.
Simplification heuristics make only local plans, by breaking the problem into subproblems. For example, many localities are stereotyped situations, such as moving through a door or turning in a corridor.

Robot Architectures

Brooks' Subsumption Architecture

This approach breaks the problem down into task-achieving behaviors (such as wandering, avoiding obstacles, or making maps) rather than decomposing it functionally (into sensing, planning, acting).
In subsumption architectures, levels of competence are stacked one on top of another, ranging from the lowest level (object avoidance) to higher levels for planning and map-making. Higher levels may interfere with lower levels, but each level's architecture is built, tested and completed before the next level is added. In this way the system is robust and incrementally more powerful.
Individual levels consist of augmented finite state machines connected by message-passing wires. Higher levels may inhibit signals on these wires, or replace them with their own signals; this is how they exercise control over more basic functions.
(For more information, see the AI Qual Summary on Agent Architectures.)

Shakey

After each action was executed, PLANES would execute the shortest plan subsequence that led to a goal and whose preconditions were satisfied. In this way, actions that failed would be retried and serendipity would lead to reduced effort. If no subsequence applied, PLANEX called STRIPS to make a new plan.

Situated Automata

This compilation approach distinguishes between the use of explicit knowledge representation by the designers (the "grand strategy") and the use of explicit knowledge within the agent architecture (the "grand tactic"). Rosenschein's compiler generates FSMs that can be proved to correspond to logical propositions about the environment, provided the compiler has the correct initial state and physics.
The FLAKEY system at SRI used situated automata to navigate, run errands, and ask questions, and had no explicit representation.

Other Architectures

No comments: