Robot Path Planning

Robot Path Planning

• Robot path planning refers to the process of determining a feasible
and optimal path for a robot to navigate from its starting position to
its goal while avoiding obstacles and adhering to certain constraints.
• This is a fundamental problem in robotics and automation, as it
enables robots to move autonomously in complex and dynamic
environments.
• The primary goal of robot path planning is to find a trajectory that
minimizes certain criteria, such as distance travelled, time taken,
energy consumption, or avoiding collisions.
Robot Path Planning
• In its most basic form, robot path planning is about finding a collision-
free motion from one position to another.
The path planning process typically involves
the following steps:
1. Perception: The robot gathers information about its surroundings
using sensors like cameras, LiDAR(Light Detection and Ranging ), or
ultrasonic sensors. This information helps in identifying obstacles,
target locations, and other relevant features.

2. Map Representation: The collected sensory data is often used to

create a representation of the environment, typically in the form of a
grid, graph, or other mathematical models. This map indicates where
obstacles are located and provides a basis for planning.
 The path planning process typically involves
the following steps:
3. Path Generation: Algorithms are used to generate potential paths
from the robot's starting position to its goal. These paths are usually a
series of connected points, waypoints, or configurations.

4. Obstacle Avoidance: The generated paths are evaluated for collisions

with obstacles. Various techniques are employed to ensure that the
generated path avoids collisions and maintains a safe distance from
obstacles.
 The path planning process typically involves
the following steps:
3. Path Generation: Algorithms are used to generate potential paths
from the robot's starting position to its goal. These paths are usually a
series of connected points, waypoints, or configurations.

4. Obstacle Avoidance: The generated paths are evaluated for collisions

with obstacles. Various techniques are employed to ensure that the
generated path avoids collisions and maintains a safe distance from
obstacles.
 The path planning process typically involves
the following steps:

5. Path Optimization: Depending on the specific criteria (e.g., shortest

path, fastest path), optimization algorithms may be used to refine the
generated path to be more efficient while still adhering to the
constraints.

6. Constraint Handling: Path planning often involves adhering to

certain constraints, such as the robot's physical limitations, dynamic
constraints, and any user-defined requirements.
 The path planning process typically involves
the following steps:

7. Execution and Monitoring: Once a suitable path is planned, the

robot can start executing the path while constantly monitoring its
environment. If unexpected obstacles or changes occur, the robot
might need to re-plan its path on-the-fly.
 Aspects of motion planning in robot path planning

1. Configuration Space and State Space:

• Configuration Space (C-Space): This is a mathematical representation of
all possible configurations a robot can take, considering all its degrees of
freedom. It helps define the robot's state in terms of its joint angles or
coordinates.
• State Space: This includes not only the robot's configuration but also
other relevant information such as velocity, acceleration, and time. It's a
more comprehensive representation of the robot's dynamics.
Aspects of motion planning in robot path planning

2. Obstacle Representation:
• Occupancy Grids: Obstacles in the environment can be represented
using occupancy grids, where each cell of the grid indicates whether it
is occupied by an obstacle or not.

• Distance Fields: These represent the distance to the nearest obstacle

at each point in the environment. They help in evaluating how close
the robot is to potential collisions.
Aspects of motion planning in robot path planning

3. Collision Detection:
• Robots need to detect collisions with obstacles or other robots. This
can involve geometric methods like bounding boxes or more complex
collision detection algorithms based on mesh representations.
Aspects of motion planning in robot path
planning
• What is meant by bounding box?
• A bounding box is an imaginary rectangle that serves as a point of
reference for object detection and creates a collision box for that
object in projects on image processing.
Aspects of motion planning in robot path planning

4. Path Representation:

• Waypoints: A sequence of discrete points that the robot must visit to

reach its goal. Connecting these waypoints generates a path.

• Trajectories: Continuous curves that represent the robot's motion

over time. Trajectories are often parameterized by time or some
other parameter.
Aspects of motion planning in robot path planning

5. Search Algorithms:
• A Algorithm: A popular graph search algorithm that finds the shortest
path between nodes while considering a heuristic to guide the search.
• Dijkstra's Algorithm: Finds the shortest path in a graph by iteratively
exploring nodes from the start node.
• RRT (Rapidly-exploring Random Trees): A probabilistic algorithm that
randomly samples the configuration space to build a tree of feasible
paths.
Aspects of motion planning in robot path planning

6. Optimization Techniques:
• Optimal Control: Formulates the path planning problem as an
optimization problem, considering robot dynamics and constraints to
find the optimal trajectory.
• Quintic Polynomials: A polynomial of degree 5. Generates smooth
trajectories using higher-order polynomials to ensure continuous
velocity, acceleration, and jerk profiles.
Aspects of motion planning in robot path planning

7. Dynamic Environments:
• In dynamic environments, robot path planning needs to account for
moving obstacles and adapt in real-time to avoid collisions.
Aspects of motion planning in robot path planning

8. Uncertainty and Sensing:

• Path planning should consider uncertainty in sensor measurements
and the environment. Techniques like probabilistic roadmaps (PRM)
and rapidly-exploring random trees with uncertainty (RRT*U) address
this.
Aspects of motion planning in robot path planning

9. Local vs. Global Planning:

• Global Planning: Involves planning the entire path from start to goal,
often in a two-step process: first, finding a feasible path, and then
refining it for optimality and smoothness.

• Local Planning: Focuses on navigating the robot around immediate

obstacles while following the global path. Reactive approaches like
potential fields can be used.
Aspects of motion planning in robot path planning

10. Constraints and Objectives:

• The path planning problem can involve multiple constraints and
objectives, such as avoiding obstacles, minimizing travel time, energy
efficiency, and adhering to kinematic or dynamic limits.
Aspects of motion planning in robot path planning

11. Human-Robot Interaction:

• If robots are operating in environments shared with humans, path
planning needs to consider social norms and human behaviour for
safe and non-intrusive navigation.
Aspects of motion planning in robot path planning

12. Real-time Execution:

• Once a path is planned, the robot needs to execute it in real-time,
adjusting for any unexpected changes in the environment.
Example of Aspects of motion planning in robot path planning
• Imagine you have a robot arm, and you want it to assemble
something using various parts. To make this happen, you provide the
robot with two types of information:
1.Models of the Parts: You give the robot detailed information about
each part, like its shape and maybe some physical properties. Think of
it as a catalog of parts.
2.Sequence of Spatial Relations: You also tell the robot the order in
which these parts should be put together. This sequence of
instructions determines how the parts fit together and where each
new part should be placed concerning the parts already assembled.
• Let's break down how the robot goes about its task using a simple
example:
• Task: Imagine you're building a toy car with the robot arm.
Example of Aspects of motion planning in
robot path planning
Example of Aspects of motion planning in robot path planning
Aspects of motion planning in robot path planning
1. Grasping a Part: The robot needs to pick up each part one by one. To
do this, it needs to know where the gripper (the part that holds things)
should be on the part it wants to pick up. It also needs a clear path to
reach that part. The gripper's position should be easily accessible,
stable, and strong enough to hold the part without dropping it.
Sometimes, the robot may need to pick up and release a part a few
times to get a good grip.
• Example: If the robot is picking up a toy car wheel, it needs to know
where on the wheel to place its gripper, so it can hold it firmly.
Aspects of motion planning in robot path planning
Aspects of motion planning in robot path planning
2. Transferring the Part: Once it has a part in its grip, the robot
needs to move it to where it's supposed to go on the car. The
robot must calculate a safe path for its arm to follow because it's
moving quickly and shouldn't bump into anything. It also needs to
ensure there's enough space around the path to prevent any
accidents.
• Example: The robot should move the wheel to the right spot on
the car's body without colliding with other parts or obstacles in
the workspace.
Aspects of motion planning in robot path planning
3. Positioning the Part on the Subassembly: Now, the robot
has to place the part precisely where it belongs on the car. This
requires careful control over its movements in a tight space.
Usually, it can't do this with a single motion; it needs a strategy
that involves multiple commands and uses information from its
sensors. It also needs to know the layout of its workspace,
including where obstacles are.
• Example: The robot needs to align the wheel perfectly with the
car's axle, and it has to do this very precisely.
Aspects of motion planning in robot path planning
• This example shows that motion planning for a robot isn't just one
problem; it's a combination of many related problems.
• Depending on the situation, you might have multiple robots working
together, moving obstacles to deal with, or even a robot hand that
can perform complex motions.
• There could also be goals like finishing the task as quickly as possible.
• Sometimes, instead of giving the robot a sequence of instructions,
you might just describe how the final assembly should look, and the
robot has to figure out the best way to get there.
Basic Problem
• In the basic motion planning problem, we're trying to figure out how a robot can
move without crashing into obstacles. To make it simpler, we assume a few
things:

1.Robot and Workspace: We imagine the robot as a single solid object (no
separate parts moving around) in a space called the workspace. This workspace
can be in 2D (like a flat surface) or 3D (like a three-dimensional space).
2.Obstacles: In this space, we have some fixed objects that don't move, and we
call them obstacles. These obstacles can be any shape, like squares or polygons.
3.No Dynamic Stuff: We don't think about how the robot moves dynamically or
how fast it moves. Instead, we focus on finding a path that keeps it away from
obstacles.
4.No Touching: We also don't deal with situations where the robot and obstacles
touch each other. We treat this as a purely geometric problem.
Basic Problem
• Now, the main problem is this:
• Problem: Imagine you have the robot in one place with a
certain orientation (the way it's facing), and you want it to go to
another place with a specific orientation, all without touching
any obstacles. Can you find a path for the robot to follow from
its starting position to its goal position without crashing into
anything? If there's no such path, you need to tell us that it's
impossible.
Basic Problem
• Imagine you have a rectangular robot, like a small book, and it needs
to move through a room filled with furniture (obstacles) to get from
one corner of the room to another. The challenge is to find a way for
the robot to move from its starting position and orientation to its
destination without bumping into any furniture.
• This basic motion planning problem might seem simple, but it's
actually quite tricky. Even though we've simplified it a lot, it's still a
tough problem. And in the real world, we can use the solutions to this
basic problem to solve more complex robot navigation tasks, like
guiding a robot through a cluttered room without collisions.
Basic motion planning problem
• Objective: The goal of the basic motion planning problem is to
explore fundamental issues before dealing with more complex
scenarios in robotics.
Basic motion planning problem
• Simplifications:
• Single Robot: We consider only one robot in the workspace. There are no
other moving objects.
• No Dynamic Considerations: We don't worry about how the robot moves
dynamically or its speed. We ignore any issues related to time.
• Non-Contact Motions: We assume that the robot's movements do not involve
physically touching or colliding with obstacles. This simplifies the problem.
• Rigid Robot: We treat the robot as a single solid object where all its points are
fixed relative to each other. This simplification makes the problem purely
geometric.
• Obstacle Constraints: The robot's movements are constrained only by the
presence of obstacles in the workspace.
Basic motion planning problem
• Problem Definition:
Basic motion planning problem
• Problem Definition:
• We assume that we accurately know the geometry of both the robot
A and the obstacles B1, B2, ..., Bq, as well as their positions in the
workspace.
• There are no restrictions on how the robot can move; it is a free-flying
object.
• The problem is to find a path T that specifies a continuous sequence
of positions and orientations for the robot A. This path should allow
the robot to move from an initial position and orientation to a goal
position and orientation without colliding with any of the obstacles
(Bi's). If no such path exists, we report failure.
 Basic motion planning problem

Illustration: basic motion planning problem. It shows how a rectangular robot (Figure a) and an L-shaped polygon
robot (Figure b) navigate through polygonal obstacles in a two-dimensional workspace.
Basic motion planning problem
• Complexity: While this basic problem may seem simple, it is
actually quite challenging. It serves as the foundation for solving
more complicated robotics problems. Solving it is also of
practical importance, as it can be applied to real-world tasks
such as mobile robot navigation.
Basic motion planning problem
Formal Statement: Some aspects of the problem, like the
concept of a "free-flying" object, may need further clarification.
One way to formalize this problem is through the configuration
space formulation, which involves creating a mathematical
representation of the robot and obstacles in a higher-dimensional
space.
Basic motion planning problem
In mathematical terms, the problem can be summarized as follows:
Given:
• A robot A with geometry and initial position and orientation.
• A set of fixed obstacles B1, B2, ..., Bq with known geometry and positions.
• A goal position and orientation for the robot A.
Find:
• A continuous path T in the configuration space that takes the robot from its
initial configuration to its goal configuration while avoiding collisions with
the obstacles.
• The configuration space formulation involves defining this configuration
space and checking if a path exists within it. The details of this formulation
can be quite complex and may require advanced mathematical techniques.
What is Configuration Space
• A key concept for motion planning is a configuration:
– a complete specification of the position of every point in the system
• A simple example: a robot that translates but does not rotate in the
plane:
– what is a sufficient representation of its configuration?
• The space of all configurations is the configuration space or C-space.
Robot Motion Planning
J.-C. Latombe (1991):

“…eminently necessary since, by definition,

a robot accomplishes tasks by moving in
the real world.”

Goals
 Collision-free trajectories
 Robot should reach the goal location
as fast as possible

42
 Problem Formulation
 The problem of motion planning can be stated as
follows. Given:
 A start pose of the robot
 A desired goal pose
 A geometric description of the robot
 A geometric description of the world

 Find a path that moves the robot gradually from

start to goal while never touching any obstacle

43
Problem Formulation

Motion planning is sometimes also called piano mover's problem

44
Configuration Space

 Although the motion planning problem is defined in the

regular world, it lives in another space: the configuration
space

 A robot configuration q is a specification of the positions of all

robot points relative to a fixed coordinate system

 Usually a configuration is expressed as vector of positions

and orientations

45
Configuration Space
Rigid-body robot example

Robot
Reference direction

y
Reference point

 3-parameter representation: q = (x,y,)

 In 3D, q would be of the form (x,y,z,,,
46
Configuration Space
Articulated robot example

q = (q1,q2,...,q10)

47
Configuration Space
 The configuration space (C-space) is the space of all
possible configurations
 The topology of this space is usually not that of a
Cartesian space
 The C-space is described as a topological manifold

 Example: wraps horizontally

and vertically!

48
Configuration Space
 Example: circular robot

 C-space is obtained by sliding the robot

along the edge of the obstacle regions
"blowing them up" by the robot radius
49
Configuration Space

50
Configuration Space
 Example: polygonal robot, translation only
Work space Configuration space

Reference point

 C-space is obtained by sliding the robot

along the edge of the obstacle regions
51
Configuration Space
 Example: polygonal robot, trans+rotation

 C-space is obtained by sliding the robot

along the edge of the obstacle regions
in all orientations
52
Configuration Space
Free space and obstacle region
 With being the work space,
the set of obstacles, the robot in
configuration

 We further define
 : start configuration
 : goal configuration

53
Configuration Space
Then, motion planning amounts to
 Finding a continuous path

with

 Given this setting,

we can do planning
with the robot being
a point in C-space!

54
What is Configuration Space
• Configuration space (C-space), also known as the state space, is a
fundamental concept in robotics used to represent all possible
configurations a robot can take, considering all of its degrees of freedom. It
is a mathematical abstraction that simplifies the representation of the
robot's motion planning problem.
• In a more detailed explanation, configuration space formulation involves
mapping the physical attributes of a robot, such as its joint angles or
coordinates, to a high-dimensional space where each dimension
corresponds to a particular degree of freedom (DOF) of the robot.
• The C-space includes all possible combinations of joint angles or
coordinates that the robot can adopt.
What is Configuration Space
• Here's how the configuration space formulation works:
• Degrees of Freedom (DOF): A robot's DOF refers to the number of
independent ways it can move. For example, a simple robot arm
might have revolute joints, which can rotate, providing rotational DOF,
while a mobile robot might have translational and rotational DOF.
• Configuration Variables: These are the values that describe the
robot's configuration in terms of its DOF. For a simple 2D robot arm
with two revolute joints, the configuration variables might be the
angles of the two joints.
What is Configuration Space
• C-Space Dimensionality: The dimensionality of the C-space is equal to
the number of configuration variables. So, for a robot with n DOF, the
C-space would be n-dimensional.
• Obstacle Representation: In the configuration space, obstacles in the
robot's environment are also represented. An obstacle can be
represented as a region in the C-space where the robot should not
move to avoid collisions.
What is Configuration Space
• Path Planning: Path planning in configuration space involves finding a
continuous or discrete path through the C-space that connects the
robot's initial configuration to its goal configuration while avoiding
collisions with obstacles. The path can be represented as a sequence
of configurations or a trajectory that the robot should follow.
• Mapping to Workspace: Once a path is planned in the C-space, it
needs to be mapped back to the robot's physical workspace. This
involves translating the configuration values back into real-world joint
angles or coordinates that the robot can follow.
Configuration Space Formulation
• Notion of Configuration Space:
1. Basic Idea: Imagine you have a robot in a certain position and
orientation in a workspace. Now, instead of thinking about the whole
robot, we'll represent it as a single point in a special space, which we
call the robot's configuration space. This helps us simplify the problem
and make the rules for the robot's movements clearer.
 Configuration Space Formulation
Notion of Configuration Space:
2. Mathematical Description:
• The robot is in a space W, which can be 2D (like a flat surface) or 3D (like a
three-dimensional space).
• The robot, denoted as A, is a compact object in W, meaning it's closed and
bounded.
• There are obstacles, B1, B2, ..., Bq, also in space W.
• We use Cartesian frames FA (moving frame) and Fw (fixed frame) to describe
the robot and the workspace, respectively.
• A configuration q of the robot A is a specific way of positioning and orienting
it. It's like telling the robot where every part of itself is relative to a fixed
reference frame.
• We represent q as (T, θ), where T describes the robot's position, and θ
describes its orientation.
Configuration Space Formulation
Dimension of Configuration Space:
1. Parameter Representation: We can describe a configuration using a
list of real numbers. For instance, we can describe the position T as
a vector of coordinates and the orientation θ as a matrix of unit
vectors.
2. Redundancy: However, this representation can be redundant
because some values don't add new information. For example, in
2D, two angles that differ by a multiple of 2π represent the same
orientation.
 Configuration Space Formulation
Dimension of Configuration Space:
3. Dealing with Redundancy:
• In 2D, we can restrict angle values to the [0, 2π) interval, using modular arithmetic
to ensure uniqueness.
• In 3D, the problem is a bit trickier, as there can be multiple valid representations
of the same orientation.

4. Dimension of C-Space (Configuration Space):

• We initially think of a configuration as having m independent parameters, where
m is 3 (for 2D) or 6 (for 3D).
• This makes us think of C-Space as R^m.
• However, C-Space is globally different from R^m. It can be divided into patches or
charts, each locally resembling R^m. When the robot moves between these
patches, we need administration to switch between parameter representations.
 Configuration Space Formulation
Dimension of Configuration Space:
• In mathematical terms:
• For 2D robots, the configuration space C is locally like R^3, and for 3D
robots, C is locally like R^6.
• Each configuration in C can be represented by a list of real
parameters, but globally, C is more complex and requires handling
transitions between patches or charts.
• So, in essence, Configuration Space is a mathematical tool used to
simplify the way we think about a robot's position and orientation,
making it easier to plan its movements while considering obstacles. It
involves describing the robot's configuration using parameters, but
these parameters can be tricky due to redundancy and global
complexities in the C-Space.
Configuration Space Formulation
Notion of a Path:
• Continuity: To define a path for the robot, we need to think about
how it moves continuously from one configuration to another. We
formalize this using a distance function.
• Distance Function: We use a distance function, denoted as d(q, q'),
which calculates how far two configurations are from each other. It
ensures that as two configurations get closer, the distance between
them tends to zero.
• A simple distance function is d(q, q') = max(||a(q) - a(q')||), where
a(q) represents the position of points on the robot in the
configuration q.
Configuration Space Formulation
Notion of a Path:
• Distance Function: We use a distance function, denoted as d(q, q'),
which calculates how far two configurations are from each other. It
ensures that as two configurations get closer, the distance between
them tends to zero.
• A simple distance function is d(q, q') = max(||a(q) - a(q')||)
• where a(q) represents the position of points on the robot in the
configuration q.
• where llx - x'll denotes the Euclidean distance between any two
points x and x' in RN.
Configuration Space Formulation
Notion of a Path:
• Path Definition: A path for the robot from an initial configuration
q_init to a goal configuration q_goal is a continuous map, represented
as tau: [0, 1] -> C.
• tau(0) = qinit and tau(1) = qgoal.
• "Free-Flying Object": This means that, when there are no obstacles,
any path for the robot from one configuration to another is possible
and feasible, as long as it is continuous.
Configuration Space Formulation
Notion of a Path:
• In mathematical terms, we use a distance function to measure the
distance between configurations in C-Space and define a continuous
path from the initial configuration to the goal configuration for the
robot. This path allows the robot to move smoothly, and the robot is
considered a "free-flying object" when no obstacles are present.
 What is Configuration Space

The robot A moves in a workspace W = RN , with N = 2 or 3.

A is modeled as a compact subset of RN.
A fixed Cartesian frame :Fw is embedded in W.
A moving Cartesian frame :FA. is embedded in A.
The configuration of A specifies the position and orientation of FA with respect to Fw.
space
Configuration Space Formulation
Basic Idea:

•We have a rigid object, which we call the robot, moving within a
physical workspace.
•The workspace is represented as an N-dimensional Euclidean space RN,
where N can be 2 or 3, with a fixed Cartesian coordinate system (frame)
Fw.
•The robot, when in a reference position and orientation, is represented
as a compact subset within RN.
•The robot has a moving frame, FA, attached to it. Every point on the
robot has fixed coordinates in this frame.
•We assume that the robot doesn't have any symmetries and isn't just a
single point.
Configuration Space Formulation
• Configuration Space (C):
• The configuration space of the robot, denoted as C, is
defined as a space where we specify the position and
orientation of the robot's moving frame (FA) with respect to
the fixed frame (Fw).
• A configuration q in C tells us where the robot's frame FA is
located and oriented within the workspace.
• We have a reference configuration, denoted as O, which is an
arbitrary choice within C.
Configuration Space Formulation
Summary,
• The configuration space C represents all possible positions and
orientations of the robot within the workspace.
• Each configuration q specifies where the robot's frame FA is
located and oriented relative to the fixed frame Fw.
• These configurations can be thought of as rigid body
transformations, and they form a non-commutative group with
respect to composition.
Robotic Motion Planning:
Configuration Space
What if the robot is not a point?

The Scout should probably not

be modeled as a point...

Nor should robots with extended

linkages that may contact obstacles...
What is the position of the robot?

Expand
obstacle(s)

Reduce
robot
 Configuration Space
• A key concept for motion planning is a configuration:
– a complete specification of the position of every point in the system

• A simple example: a robot that translates but does not rotate in the
plane:

– what is a sufficient representation of its configuration?

• The space of all configurations is the configuration space or C-

space.
 Robot Manipulators
What are this arm’s forward kinematics?
(How does its position
(x,y) depend on its joint angles?)


L2

y
L1

x
 Robot Manipulators
What are this arm’s forward kinematics?
(x,y)
 Find (x,y) in terms of  and  ...

L2

y
L1

x

Keeping it “simple”
c = cos() , s = sin()
c = cos() , s = sin()
c= cos() , s= sin()
 Manipulator kinematics

x L1c L2c Position

(x,y) = +
 y L1s  L2s 
L2

y
L1

x

Keeping it “simple”
c = cos() , s = sin()
c = cos() , s = sin()
c= cos() , s= sin()
 Inverse Kinematics
Inverse kinematics -- finding joint angles from Cartesian coordinates
via a geometric or algebraic approach...
L2 (x,y)


L1


Given (x,y) and L1 and L2  what are the values of    

 Inverse Kinematics
Inverse kinematics -- finding joint angles from Cartesian coordinates
via a geometric or algebraic approach...
L2 (x,y)
 x2 + y2 - L 2 - L 2

 = cos
-1

1 2

2L1L2
L1

 = 180 - 

L2 sin()
 = sin-1 + tan-1(y/x)
x2 + y2
(1,0) = 1.3183, -1.06 atan2(y,x)
(-1,0) = 1.3183, 4.45
Some Other Examples of C-Space
• A rotating bar fixed at a point
– what is its C-space?
– what is its workspace

• A rotating bar that translates along the rotation axis

– what is its C-space?
– what is its workspace

• A two-link manipulator
– what is its C-space?
– what is its workspace?
– Suppose there are joint limits, does this change the C-space?
– The workspace?
 Configuration Space
Where can we put qB ?

360

A qA
270
 B
180


 90

0 
45 90 135 180
An obstacle in the robot’s workspace Torus
(wraps horizontally and vertically)
Obstacles in C-Space
• Let q denote a point in a configuration space Q

• The path planning problem is to find a mapping c:[0,1] Q s.t. no

configuration along the path intersects an obstacle

• Recall a workspace obstacle is WOi

• A configuration space obstacle QOi is the set of configurations q at which

the robot intersects WOi, that is
– QOi = {q  Q | R(q)  WOi  }

• The free configuration space (or just free space) Qfree is

Qfree = Q \ ( QOi )

The free space is generally an open set

A free path is a mapping c:[0,1] Qfree
A semifree path is a mapping c:[0,1] cl(Qfree)
 Disc in 2-D
workspace
workspace configuration
workspace
space
 Example of a World (and Robot)

Free Space

Obstacles

Robot
x,y
 Configuration Space:
Accommodate Robot Size

Free Space

Obstacles

Robot
x,y (treat as point object)
Trace Boundary of
Workspace

Pick a reference point…

Polygonal robot translating in 2-D
workspace

workspace configuration
space
Polygonal robot translating & rotating in 2-
D workspace

workspace configuration
space
 Any reference point

R
y
45 degrees

x
 Any reference point configuration

Taking the cross section of configuration space

in which the robot is rotated 45 degrees...

R
y
45 degrees

P
 Any reference point configuration

Taking the cross section of configuration space

in which the robot is rotated 45 degrees...

R
y
45 degrees

P
 Minkowski
sum
• The Minkowski sum of two sets P and Q, denoted by PQ, is
defined as
P+Q = { p+q | p P, qQ }

q
• Similarly, the Minkowski difference is defined as
P – Q = { p–q | pP, qQ } p
Minkowski sum of convex polygons
• The Minkowski sum of two convex polygons P and Q of m and n
vertices respectively is a convex polygon P + Q of m + n vertices.
– The vertices of P + Q are the “sums” of vertices of P and Q.
 Observation
• If P is an obstacle in the workspace and M is a moving object. Then the C-
space obstacle corresponding to P is P – M.

O
 Star Algorithm: Polygonal Obstacles

e1

r1

r3 r2 e2
e4

e3
e1
r2 r3

e4 e2

e3 r1
 Star Algorithm
e1

e4 e2

e3
r1
e1

r2 e4 e2

r3
e3
 Configuration Space “Quiz”
Where do we put ?

360

A qA
270
 B
180


 90

qB
0 
45 90 135 180
An obstacle in the robot’s workspace Torus
(wraps horizontally and vertically)
 Configuration Space Obstacle
How do we get from A to B ?
Reference configuration

360
qA
A 270
 B
180


 90

qB
0 
45 90 135 180
An obstacle in the robot’s workspace
The C-space representation
of this obstacle…
Two Link Path(path exists)
Two Link Path(not exist)
 Additional dimensions
What would the configuration space of a
rectangular robot (red) in this world look like?
Assume it can translate and rotate in the plane.
(The blue rectangle is an obstacle.)

x
a 2d possibility
2d projection...

x
A problem?

qinit

qgoal
Requires one more d…

qinit

qgoal
too conservative !
what instead?
When the robot is at one orientation

qinit

qgoal it can make it...

0º
When the robot is at another orientation

qinit

qgoal it depends...
 Additional dimensions
What would the configuration space of a
rectangular robot (red) in this world look like?
(The obstacle is blue.)

y 180º

90º

0º
this is twisted...
Polygonal robot translating & rotating in 2-
D workspace

y

x
SE(2)
2D Rigid Object
 The Configuration Space (C-space)
θ1 θ2 θ3
θ3

TOP θ3
VIEW

θ1
θ2
θ2

θ1

workspace C-space
Moving a Piano
 Configuration Space (C-space)
q0 q1
INIT:
q2 Q(0)
qn
Q(t)
q4 q3
GOAL:
q0 (t) Q(T)
 
Q(t)   ⁝  t  
qn (t) 
Parameterizations of SO(2) (2D Rotations):
• Basic Idea:
• In 2D, we're dealing with rotations, like turning a robot
around a fixed point in a flat plane.
• To represent these rotations, we need a way to describe
angles.
• However, angles alone aren't perfect because multiple angles
can represent the same rotation
• (e.g., 45 degrees and 405 degrees represent the same
rotation).
Parameterizations of SO(2) (2D Rotations):
• Angle Parameterization:
• One simple way to represent rotations in SO(2) is by using a single
angle (θ), which measures the rotation from a reference orientation.
• However, this representation has a problem: it's not one-to-one
because multiple angles can represent the same rotation (angles
differing by multiples of 360 degrees).
• To make this work as a chart, we need to restrict the angle θ to an
open interval of length 2π (e.g., between 0 and 2π).
• We could use two such intervals, like [0, 2π) and [-π, π), to create an
atlas. An atlas is a collection of charts covering all possible rotations.
Parameterizations of SO(2) (2D Rotations):
• Stereographic Projection Parameterization:
• Another way to represent rotations is through stereographic projection.
• Imagine you have a unit circle except for one point (P) in 2D space.
• You project this circle onto a line (L) tangent to the circle, and the origin of the
line is at the point of tangency (O).
• Now, imagine drawing a line from point P to the opposite side of the circle,
intersecting the circle at Q and the line L at R.
• The stereographic projection maps every point Q on the circle (except P) to a
point R on the line L.
• In regions not including P, this mapping is one-to-one and can define a chart.
• You can create two stereographic charts using two different points (P) on the
circle to cover all rotations in SO(2). These charts together form an atlas.
Parameterizations of SO(2) (2D Rotations):
• Stereographic Projection Parameterization:
Parameterizations of SO(2) (2D Rotations):
• Mathematical Explanation:
• In SO(2), we want to represent rotations using parameters.
• One parameterization uses a single angle (θ), but it's not one-to-one,
so we restrict θ to an open interval (e.g., [0, 2π)) and use two such
intervals to create an atlas.
• Another parameterization, called stereographic projection, maps
points on a unit circle (except one point) to a line tangent to the
circle. In regions not including the excluded point, this mapping is
one-to-one and can be used to create charts. Two stereographic
charts, created with two different excluded points, form an atlas.
Parameterizations of SO(2) (2D Rotations):
Quaternions:
• Quaternions are a mathematical tool used to represent orientations
in a three-dimensional space.
• They consist of four parameters and are quite useful for various
applications, including robotics and computer graphics.
Quaternions:
• Components of a Quaternion:
• A quaternion, denoted as X, has four parts: a scalar part (X₀) and a
3D vector part (x).
• These parts are combined using addition, so X = X₀ + x.
• In some cases, 3D vectors can be treated as quaternions with a zero
scalar part, and scalars can be treated as quaternions with a zero
vector part.
Quaternions:
• Quaternion Multiplication:
• When you multiply two quaternions, P and Q, you get a new
quaternion R.
• This multiplication involves both the scalar and vector parts:
• R₀ = P₀ * Q₀ - (P ⋅ Q)
• Rᵥ = P₀ * Q + Q₀ * P + (P × Q)
• Here, ⋅ represents the inner product, and × represents the cross
product of vectors.
• This multiplication is linear, meaning it satisfies properties like
distributivity and associativity.
Quaternions:
• Conjugate of a Quaternion:
• The conjugate of a quaternion X is denoted as X* and is defined as:
• X* = X₀ - x
• The product of a quaternion X and its conjugate X* results in a non-
negative scalar:
• X * X* = |x|²
• The length of X in Euclidean space is the square root of this scalar:
||X|| = √(X * X*).
Quaternions:
• Unit Quaternions:
• A unit quaternion is a quaternion with a length of 1, meaning ||X|| = 1.
• Unit quaternions are commonly used to represent rotations in three-
dimensional space.
• They can represent a rotation around a unit vector n by an angle θ
with a specific formula:
• X(θ) = (cos(θ/2), n * sin(θ/2))
• Here, n represents the unit vector along which the rotation occurs.
Quaternions:
• Mapping to Projective 3-Space:
• Unit quaternions are used to map to projective 3-space (p³), a
topological space.
• In p³, antipodal points (opposite points on the unit sphere) are
identified.
• This space is topologically equivalent to SO(3), the space of 3D
rotations.
.
Quaternions:
• Constructing an Atlas of SO(3):
• Unit quaternions are used to create an atlas (a collection of charts)
for representing SO(3), the space of 3D rotations.
• Each chart (Ui, ϕi) covers a portion of SO(3) and is defined based on
the largest-magnitude component of the unit quaternion.
• These charts help represent rotations efficiently and are useful in
various applications, especially in robotics and motion planning.
Quaternions:
• In summary, quaternions are a mathematical representation of
orientations in 3D space, and unit quaternions are particularly
valuable for representing rotations. They allow us to efficiently work
with 3D rotations and are used extensively in fields like computer
graphics and robotics.
 Topology?

Sphere? Torus?

2R manipulator

Configuration space
Why study the Topology

• Extend results from one space to another: spheres to stars

• Impact the representation
• Know where you are
• Others?
Why study the Topology

• Extend results from one space to another: spheres to stars

• Impact the representation
• Know where you are
• Others?
The Topology of Configuration Space
• Topology is the “intrinsic character” of a space

• Two space have a different topology if cutting and pasting is

required to make them the same (e.g. a sheet of paper vs. a
mobius strip)
– think of rubber figures --- if we can stretch and reshape “continuously”
without tearing, one into the other, they have the same topology

• A basic mathematical mechanism for talking about topology is

the homeomorphism.
Homeomorphism and Diffeomorphisms
• Recall mappings:
– : S  T
– If each elements of  goes to a unique T,  is injective (or one to one)
– If each element of T has a corresponding preimage in S, then  is surjective
(or onto).
– If  is surjective and injective, then it is bijective (in which case an inverse, -1
exists).
–  is smooth if derivatives of all orders exist (we say  is C)

• If : S  T is a bijection, and both  and -1 are continuous,  is a

homeomorphism; if such a  exists, S and T are homeomorphic.

• If homeomorphism where both  and -1 are smooth is a diffeomorphism.

Some Questions:
What is a homeomorphism, and how does it relate to the
properties of Injectiveness and surjectiveness of a
mapping

• A homeomorphism is a continuous bijective mapping (function)

between two topological spaces S and T, such that both the function
and its inverse are continuous.
• It is a way to establish a correspondence between the points of two
spaces while preserving their topological properties.
• Injectiveness means that each element in S maps to a unique element
in T, and surjectiveness means that each element in T has a
corresponding preimage in S.
Some Questions:
Explain the concept of a diffeomorphism and how it
differs from a homeomorphism?

• A diffeomorphism is a special type of homeomorphism that also

preserves smoothness.
• In other words, if a mapping (function) φ: S → T is a diffeomorphism, it
is a bijective function where both φ and its inverse φ⁻¹ are smooth,
meaning that they have derivatives of all orders.
• Diffeomorphisms are commonly used in the context of differentiable
manifolds in differential geometry.
Some Questions:
In the context of mappings, what does it mean for a
function to be smooth and have derivatives of all orders?

• When we say a function φ is smooth (C∞), it means that it has

derivatives of all orders.
• This implies that the function is infinitely differentiable, and its
derivative exists and is continuous.
• Smooth functions are essential robot path planning
Some Questions:
What is the significance of a bijection in the context of
mappings, and why is it important in establishing
homeomorphisms and diffeomorphisms?

• A bijection is a one-to-one correspondence between the elements of

two sets, S and T.
• In the context of mappings, it means that every element in S maps to a
unique element in T, and vice versa.
• The importance of a bijection lies in its ability to establish a one-to-one
relationship, which is a fundamental requirement for constructing both
homeomorphisms and diffeomorphisms.
Some Questions:
How do you determine if two spaces, S and T, are
homeomorphic?

• Two spaces, S and T, are considered homeomorphic if there exists a

homeomorphism φ: S → T, where φ and its inverse φ⁻¹ are both
continuous.
• In other words, if you can find a continuous, bijective mapping that
preserves the topological structure between the two spaces, they are
homeomorphic..
Some Questions:
Can you provide an example of a mapping that is injective
but not surjective, and vice versa?

• An example of a mapping that is injective but not surjective is φ: ℝ →

ℝ defined as φ(x) = x².
• This function takes each element in ℝ to a unique value but does not
cover the entire range of ℝ, so it is not surjective.
• Conversely, a surjective but not injective example would be
φ: ℝ → [0, ∞) defined as φ(x) = x², which covers all non-negative values
but maps multiple inputs to the same output.
Some Questions:
Are there any limitations or conditions under which a
mapping cannot be a diffeomorphism, even if it is a
homeomorphism?

• There can be situations where a mapping is a homeomorphism but not

a diffeomorphism.
• This occurs when the mapping preserves topological properties
(making it a homeomorphism) but does not preserve the smoothness
of the functions and their derivatives (making it not a diffeomorphism).
• To be a diffeomorphism, a mapping must be both continuous and
smooth, which is a stronger condition than just continuity required for
a homeomorphism.
 Some Examples
• How would you show a square and a rectangle are diffeomorphic?

• How would you show that a circle and an ellipse are diffeomorphic (implies both
are topologically S1)……yes

• Interestingly, a “racetrack” is not diffeomorphic to a circle

– composed of two straight segments and two circular segments
– at the junctions, there is a discontinuity; it is therefore not possible to construct a smooth map!
– How would you show this (hint, do this for a function on 1 and think about the chain rule)
– Is it homeomorphic?
• How would you show a square and a rectangle are
diffeomorphic?
• A square and a rectangle are not diffeomorphic.
• While they are homeomorphic in the sense that they have the same topological properties,
including the same number of holes (in this case, none), they are not diffeomorphic
because diffeomorphisms require both homeomorphism and smoothness.
• A diffeomorphism is a bijective mapping between two differentiable manifolds (in this case,
geometric shapes) such that both the mapping and its inverse are smooth (meaning they
have derivatives of all orders). In the case of a square and a rectangle with sides of different
lengths, no such smooth bijective mapping exists because the square has constant
curvature at all points, while the rectangle has varying curvature along its sides.
• In simpler terms, the square has uniform smoothness and curvature, while the rectangle
has varying smoothness and curvature, which makes it impossible to find a smooth
bijection between the two shapes and their corresponding tangent spaces.
• Therefore, a square and a rectangle are not diffeomorphic.
“Racetrack” is not diffeomorphic to a circle
• The racetrack is not diffeomorphic to a circle due to the presence of corners or
junctions within the racetrack.
• These corners introduce discontinuities in the smoothness of any potential mapping.
• To illustrate this formally, consider defining a function on the real line ℝ¹ to model
the racetrack shape. This function, denoted as f: ℝ¹ → ℝ¹, should represent the
racetrack's geometry, including its corners.
• When we apply the chain rule in calculus to this function, it becomes evident that
when a function has corners or discontinuities, its derivative may not exist at those
specific points.
• In contrast, the circle does not contain any corners or discontinuities in its geometry.
• As a result, the derivatives of the circle's points exist at all locations.
• The lack of smoothness in the racetrack function prevents it from being a
diffeomorphism to the circle. Diffeomorphisms require both the mapping and its
inverse to be smooth.
• However, it's important to note that the racetrack and the circle can still be
homeomorphic. Homeomorphisms only necessitate continuity and a continuous
inverse, not necessarily smoothness.
 Manifolds
• A space S locally diffeomorphic (homeomorphic) to a space T if each p S
there is a neighborhood containing it for which a diffeomorphism
(homeomorphism) to some neighborhood of T exists.

• S1 is locally diffeomorphic to 1
• The sphere is locally diffeomorphic to the plane (as is the torus)

• A set S is a k-dimensional manifold if it is locally homeomorphic

to k
 Manifolds
• A space S locally diffeomorphic (homeomorphic) to a space T if each p S
there is a neighborhood containing it for which a diffeomorphism
(homeomorphism) to some neighborhood of T exists.

• S1 is locally diffeomorphic to 1 Every planes combine creates atlas

• The sphere is locally diffeomorphic to the plane (as is the torus)

• A set S is a k-dimensional manifold if it is locally homeomorphic

to k
 Manifolds
• A space S locally diffeomorphic (homeomorphic) to a space T if each p S
there is a neighborhood containing it for which a diffeomorphism
(homeomorphism) to some neighborhood of T exists.

• S1 is locally diffeomorphic to 1
• The sphere is locally diffeomorphic to the plane (as is the torus)

• A set S is a k-dimensional manifold if it is locally homeomorphic

to k
 Manifolds
• A space S locally diffeomorphic (homeomorphic) to a space T if each p S
there is a neighborhood containing it for which a diffeomorphism
(homeomorphism) to some neighborhood of T exists.

• S1 is locally diffeomorphic to 1
• The sphere is locally diffeomorphic to the plane (as is the torus)

• A set S is a k-dimensional manifold if it is locally homeomorphic

to k
Charts and Differentiable Manifolds
• A Chart is a pair (U,) such that U is an open set in a k-dimensional manifold and  is a
diffeomorphism from U to some open set in  k

– think of this as a “coordinate system” for U (e.g. lines of latitude and longitude away form
the poles).
– The inverse map is a parameterization of the manifold

• Many manifolds require more than one chart to cover (e.g. the circle requires at least 2)

• An atlas is a set of charts that

– cover a manifold
– are smooth where they overlap (the book defines the notion of C related for this; we will
take this for granted).

• A set S is a differentiable manifold of dimension n if there exists an atlas from S to n

– For example, this is what allows us (locally) to view the (spherical) earth as flat and talk
about translational velocities upon it.
Charts and Differentiable Manifolds
• A Chart is a pair (U,) such that U is an open set in a k-dimensional manifold and  is a
diffeomorphism from U to some open set in  k

– think of this as a “coordinate system” for U (e.g. lines of latitude and longitude away form
the poles).
– The inverse map is a parameterization of the manifold

• Many manifolds require more than one chart to cover (e.g. the circle requires at least 2)

• An atlas is a set of charts that

– cover a manifold
– are smooth where they overlap (the book defines the notion of C related for this; we will
take this for granted).

• A set S is a differentiable manifold of dimension n if there exists an atlas from S to n

– For example, this is what allows us (locally) to view the (spherical) earth as flat and talk
about translational velocities upon it.
 Some Minor Notational Points
• 1  1  ...  1 = n
• S1  S1  ...  S1  Sn (= Tn, the n-dimensional torus)
• Sn is the n-dimensional sphere

• Although Sn is an n-dimensional manifold, it is not a manifold of a

single chart --- there is no single, smooth, invertible mapping
from Sn to Rn ---
– they are not ??morphic?
Examples
More on dimension
More Example Configuration Spaces (contrasted with workspace)
• Holonomic robot in plane:
– workspace 2
– configuration space 2

• 3-joint revolute arm in the plane

– Workspace, a torus of outer radius L1 + L2 + L3
– configuration space T3

• 2-joint revolute arm with a prismatic joint in the plane

– workspace disc of radius L1 + L2 + L3
– configuration space T2  

• 3-joint revolute arm mounted on a mobile robot (holonomic)

– workspace is a “sandwich” of radius L1 + L2 + L3
 2  T3

• 3-joint revolute arm floating in space

– workspace is 3
– configuration space is T3
Parameterization of Torus
 2d Manifolds

real plane cylinder torus

projective plane mobius strip klein bottle

Representing Rotations
• Consider S1 --- rotation in the plane

• The action of a rotation is to, well, rotate --> R: 2  2

• We can represent this action by a matrix R that is applied

(through matrix multiplication) to points in 2

cos( - sin(
sin( cos(

• Note, we can either think of rotating a point through an angle, or

rotate the coordinate system (or frame) of the point.
 A Few Final Definitions
• A manifold is path-connected if there is a path between any two
points.

• A space is compact if it is closed and bounded

– configuration space might be either depending on how we model things
– compact and non-compact spaces cannot be diffeomorphic!

• With this, we see that for manifolds, we can

– live with “global” parameterizations that introduce odd singularities (e.g. angle/elevation on a sphere)
– use atlases
– embed in a higher-dimensional space using constraints

• Some prefer the later as it often avoids the complexities associated

with singularities and/or multiple overlapping maps