Robot Motion Planning and Computer Vision

Robot Motion Planning Book Overview

• The book focuses on the central theme of motion planning, which is necessary for autonomous robots to achieve goal arrangements of physical objects.
• Motion planning involves deciding what motions to perform to achieve a goal, which is a challenging problem in robotics.

Configuration Space Concept

• The concept of configuration space is used throughout the book to organize the various facets of motion planning in a coherent framework.
• Configuration space treats the robot as a point in an appropriate space, representing the geometry of the task.
• Physical concepts, such as force and friction, can be represented in this space as additional geometrical constructs.

Book Structure

• The book consists of 11 chapters, with the first half focusing on the basic motion planning problem and the second half exploring extensions of this problem.
• Chapters 2 and 3 develop the notion of configuration space for a rigid object that can translate and rotate freely among obstacles in a two- or three-dimensional workspace.
• Chapters 4-7 describe four computational approaches for solving the basic motion planning problem: the roadmap approach, exact and approximate cell decomposition approaches, and the potential field approach.
• Chapters 8-11 present various extensions of the basic motion planning problem, including moving obstacles, multiple robots, nonholonomic kinematic constraints, uncertainty, and motion planning with movable objects.

Key Concepts and Techniques

• The book covers key concepts and techniques in motion planning, including:
  • Collision-free path planning
  • Obstacles in configuration space
  • Roadmap methods
  • Exact and approximate cell decomposition
  • Potential field methods
  • Kinematic constraints
  • Dealing with uncertainty
  • Motion planning with movable objects

Assumed Knowledge

• The book assumes good "undergraduate-level" knowledge in mathematics (geometry, topology, algebra) and algorithms.
• A glossary of mathematical definitions is provided in Appendix A for the reader's convenience.
• Background in robotics and mechanics is also assumed.### Notations and Definitions
• An element of a configuration (Le.a configuration) is denoted by q
• The region of the workspace occupied by the robot A at configuration q is denoted by A(q)
• An obstacle B in the workspace maps to a region called C-obstacle and denoted by CB
• The free space in configuration space is denoted by Cfree, the contact space by Ccontact, and Cvalid = Cfree U Ccontact is the valid space
• A path is denoted by r, and it is usually a function of a parameter denoted by s that takes its values in the interval [0,1]
• A vector is denoted by a symbol with an arrow on top of it, e.g. v, and its modulus is written ||v||
• The inner product of two vectors v1 and v2 is denoted by or v1.v2, and the outer product of v1 and v2 is denoted by v1 A v2
• The angle between v1 and v2 is written angle(v1, v2)
• The distance between two points x and y of a Euclidean space is denoted by ||x - y||
• An interval in R bounded by a and b is denoted by [a, b] if it is closed at both ends, and by (a, b) if it is open at both ends
• The symbols Ef) and e are the Minkowski operators for affine set addition and subtraction, respectively
• Let E be a topological space and F be a subset of it. cl(F), int(F), and B(F) denote the closure, the interior, and the boundary of F, respectively
• Most of the time, calligraphic letters, e.g. S, denote sets
• Symbols in typewriter type style are used to denote boolean expressions or predicates, e.g. CB, Achieve

Aspects of Motion Planning

• A robot is a versatile mechanical device, e.g. a manipulator arm, a multi-joint multi-fingered hand, a wheeled or legged vehicle, a free-flying platform, or a combination of these
• A robot operates in a workspace within the real world, populated by physical objects and subject to the laws of nature
• The robot performs tasks by executing motions in the workspace
• The capability of planning its own motions, i.e. deciding automatically what motions to execute in order to achieve a task, is a major undertaking in robotics

Basic Problem

• The basic motion planning problem is defined as:
  • Let A be a single rigid object - the robot - moving in a Euclidean space W, called workspace, represented as R^N, with N = 2 or 3
  • Let B1, ..., Bq be fixed rigid objects distributed in W
  • The problem is: Given an initial position and orientation and a goal position and orientation of A in W, generate a path r specifying a continuous sequence of positions and orientations of A avoiding contact with the Bi's, starting at the initial position and orientation, and terminating at the goal position and orientation
  • Report failure if no such path exists

Configuration Space Formulation

• The configuration space of A is the space C of all the configurations of A
• A configuration q of A is a specification of the position T and orientation θ of FA with respect to Fw
• The subset of W occupied by A at configuration q is denoted by A(q)
• The point a on A at configuration q is denoted by a(q) in W
• C is a differentiable manifold of dimension m, where m = N(N + 1)

Manifold Structure

• C is a manifold of dimension m, where m = N(N + 1)
• C can be covered by a finite number of charts
• The charts in an atlas are C^∞-related, which allows us to extend the differential properties established in a chart of the atlas to all the other charts
• The Whitney Embedding Theorem states that every r-dimensional manifold can be embedded in R^2r### Introduction to Configuration Space
• Configuration space (C) is a space where a robot's position and orientation are represented as a single point
• The concept of C-obstacles is introduced, which are regions in C where the robot collides with obstacles in the workspace

Case of a Polygonal Workspace

• The case of a polygonal workspace is examined, where a polygon A moves freely in the plane among obstacles modeled as polygonal regions
• Two representations of C-obstacles are constructed: a predicate CB and an explicit description of the boundary of CB

Polygonal Regions and Polygons

• A convex polygonal region in R2 is defined as the intersection of a finite number of closed half-planes
• A polygonal region is a subset of R2 obtained by taking the union of a finite number of convex polygonal regions
• A polygon is a polygonal region that is homeomorphic to the closed unit disc
• A polygon has a boundary that is a closed-loop sequence of line segments forming a Jordan curve

Type A and Type B Contacts

• Two types of contact between the robot A and an obstacle B are defined:
  • Type A contact: an edge of A contains a vertex of B
  • Type B contact: a vertex of A is contained in an edge of B
• The type of contact is determined by the constraint that the interiors of A and B do not overlap
• Type A contact requires a subrange of orientations of A for feasibility