Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MECEE 4602: Introduction to Robotics
Motion Planning and Navigation
1 Arm Configuration Space
How is the problem of a mobile robot navigating around a room similar to that of a robot arm?
At first glance, they appear quite different:
To see the similarities, we must think of the arm movement problem in joint space. We recall
once again that this is the space of all values for the joints. A point in joint space is denoted by
q = [q0, .., qn−1]
T ∈ Rn
, where n is the number of joints of the robot. Note that, in this context,
the joint space of a robot is often referred to as the configuration space.
Here is an approximate example of the joint space of the 2-link robot marking an obstacle as
well as joint limits for the second joint:
x
y
q
1
q
2 current
pose
If a point in joint space is marked as “impossible”, it means that that combination of joint
angles should not be used. Reasons can include:
• robot is in collision with the environment;
• robot is in collision with itself;
• joint limits are violated;
• etc.
Once we are operating in configuration space, we see that the motion planning problem starts
resembling the case for mobile robot: we have a start location, a goal location, and a number of
obstacles along the way. The current pose of the robot gives us the start location in configuration
space. Performing IK on the goal end-effector pose gives us a goal location (or multiple goal
locations) in configuration space. The robot must then “navigate” its way around obstacles to
reach the goal.
2 Building a configuration space map
2.1 Polygonal vs. grid-based maps
A polygonal map is just a list of obstacles, each expressed as a polygon.
In contrast, a grid-based map is a dense grid, sampling the entire space. The simplest version
is a binary grid: each cell contains either a 0 (indicating free space) or a 1 (indicating an obstacle).
More complex grids can also hold other types of information in their cells. (Example below from
Peter Corke, “Robotics, Vision and Control”).
The pros and cons of polygonal maps vs. grids include:
• polygonal maps are much more compact in memory;
• grid-based maps allow for fast testing if a point is inside an obstacle or not;
• grid-based maps are much easier to build for many real-world problems.
Our algorithms and examples will focus almost exclusively on grid-based maps, as they are used
in practice much more often.
2.2 Mobile robots
For mobile robots, the configuration space is closely related to the Cartesian space. For a robot
navigating in 2 dimensions, a configuration consists of an [x, y, θ] triple showing the coordinates of a
reference point chosen somewhere on the robot, as well as the orientation of the base relative to the
world. In general, the configuration space of a robot capable of 2D navigation is thus 3-dimensional.
If the robot has a round footprint, its orientation does not matter for the purpose of collision
avoidance. The configuration space is thus considered to be 2-dimensional, containing just [x, y],
the coordinates of the reference point.
Assume we have a Cartesian map showing the locations of obstacles in the world. Obviously, if
a point [a, b] is inside an obstacle in this map, it should also be marked as infeasible in the configuration space – the robot reference point can not be inside an obstacle. However, the configuration
space map has to contain more than that: the robot can collide with an obstacle even if its reference
point is not inside the obstacle, but merely too close to it.
The common solution to that problem is to “grow” or “inflate” the obstacles by the footprint
of the robot when building the configuration space map. This allows us to think of the robot as a
single point in configuration space; as long as that point is in feasible territory, the entire robot is
safe.
For non-round robots, we can still “inflate” all obstacles by a radius large enough to accomodate
the robot in any orientation. This then allows us to again have a 2-dimensional configuration space,
where we only care about x and y. The flip side is that we inflate the obstacles more than is strictly
needed, we might close off passageways that actually can be traversed.
We note that if we start with a polygonal map of Cartesian space (that is, a list of polygons
making up the obstacles), this method will result in a polygonal map of configuration space as well.
2.3 Robot arms
For a robot arm, we could theoretically build a polygonal configuration space by starting from a
Cartesian map of the environment, then performing Inverse Kinematics to map obstacles to the
configuration space. However, this is extremely impractical. Most often, arm configuration space
maps are grid based, and built simply by sampling the grid and determining if the point is feasible
or not through forward kinematics.
Note that some algorithms require the entire configuration space to be mapped in advance.
Others only require us to sample the space as needed to find out if a given point is acceptable or
not.
3 Planning in configuration space
Many algorithms for planning in configuration space fall in the broad category of graph search
algorithms. A graph is a colection of nodes and edges, where each edge can have an associated
cost of traversing.