597 Notes

CSE 597F Intelligent Robotics
Lecture Notes: Sept 16 & 21

Topics Covered

Motion Planning Methods

Cell Decomposition Methods

Overview
Exact Methods

Sweep Line

Approximate Methods

Quadtrees

Potential Field Based Method

Overview
Force Equations
Algorithm

Cell Decomposition

Overview

The goal of vertical decomposition methods in robot navigation centers around partitioning C_free into a discrete number of cells. A connectivity graph can then be formed linking these areas. Using this graph, a free path for the robot's travels may then be found.

There are two main types of cell decomposition approaches:

Exact Methods

-Creates a set of cells which completely covers C_free

-can yield complicated cells with irregular boundaries

-can be difficult to compute efficient traversals through cells.

Approximate Methods

-Creates a set of cells which approximately covers C_free.

-can yield simpler cells with regular boundaries

-easier to compute traversals, but information regarding terrain is incomplete.

Exact Methods

C_free is decomposed into a discrete number of cells such that the union of cells exactly covers the free C-Space. A connectivity graph may then be constructed which connects the centroids of each adjacent cell. This graph may be weighted to reflect the varying distances between each centroid.

Sweep Line Algorithm(for convex polygonal obstacle spaces)

1) Sort Vertices of the Obstacle Space(CB) by x-coordinate.

2) 'sweep' a vertical line L from left to right, stopping at each vertex V in CB.

            3) Three cases are now possible at each stop or 'event':

                1. One vertex edge is to the left, and one vertex edge is to the right of L.
                        In this case end the current cell and begin a new cell.

2. Both vertex edges are to the right of the scan line.
In this case end the two current cells and begin a new cell.

3. Both vertex edges are to the left of the scan line.
In this case end the current cell and begin two new cells.

To obtain this information, maintain a list of edges which L is currently intersecting. Update this list at each 'event' and check how many edges have been removed or added.

Note: This algorithm run in O(n log n) time and is complete.

Example:

An example of several events in the scan lines progression illustrates the algorithm.

Beginning at the leftmost edge, scanning leftward:

Event	Status	Case Followed
start	{B,C}
a	{B,C,D,E}	#2
b	{B,C,E,F}	#1
d	{B,C,E,F,H,I}	#2

Approximate Methods

The goal of approximate decomposition methods is to break C_free into a set of connected cells which describe the general characteristics of the cell's enclosed area. Exact methods would tell you exactly where obstacle boundaries lie within each cell, whereas approximate methods only tell you that an obstacle exists somewhere in the cell. Generally, each cell C is then broken down further into subcells which describe the general characteristics of the cell's quadrants. One may continue to break the subcells down further until the desired resolution is achieved.

Some Advantages of Approximate methods are:

Cells have a simple standard shape so it is simple to compute the decomposition.
Due to the cells simplistic geometry, computing a path between the cells is often simpler than the exact decomposition.

Quadtree Algorithm

One example of the approx. cell decomposition method is the Quadtree Algorithm. This algorithm represents C-Space as a quadtree structure by performing the following operations:

1. Place C-Space as the root node and current cell.

2. Break current cell into n non-overlapping cells.

3. Check each cell for obstacles, noting if obstacles take up all, some, or none of the cell.

4. Represent each of these nonoverlapping cells as children nodes.

5. If a cell is completely free, or completely taken up by obstacles it has no children,

as the characteristics of the entire cell are known.

6. If a cell is mixed(partially free, partially taken up by obstacles) repeat this process by

returning to step 2.

    Note: Once the desired resolution is achieved, you may stop the algorithm at any time,
              create a connectivity graph based on the quadtree and compute a path through
              the known portions C_free.

This algorithm is resolution complete, meaning that it guarantees that if a soution exists at the current resolution, it will be found.

Example:

Potential Field Based Navigation:

Overview

An alternative to the static and preplanned Decomposition navigation methods, is a Potential Field Based approach. Drawing from the field theory concept in physics, this method models obstacles as emitting a repellant force and the goal point as emitting an attractive force on our robot. Navigation is performed by
moving the robot so as to minimize its potential energy in our field. The point of minimal potential will ideally be the goal point. The benefits of this approach are:

Simple extendability to higher dimension workspaces.
Dynamic decisions about robot's path, which allow for motion in changing environments.

A major drawback to this approach, however, is that:

Method is incomplete if local minima exist in the potential function.

As the example below shows for the 1 dimensional case, a traveling robot will become become stuck in a local potential minima on its way to the Goal:

Force Equations

For this method to be effective equations, attractive and repellant forces must have the following properties:

Attractive & repellant potential functions should be differentiable across the workspace.
Attractive Force should increase as robot moves away from goal.
Repulsive Force should decrease as the robot moves away from obstacles.

Attractive Force
One possiblility for the attractive force in 2 dimensions is a parabolic well of the form:

        V_a=C_a[(x-x_g)² + (y-y_g)²]
            where:
            C_a= Attractive Force Constant
            (x_g,y_g) = Goal Point

    Repulsive Force
         The following piecewise equation is simple to evaluate and satisfies our criteria for the
        repulsive force in 2 dimensions:

        V_r=[1/d(x,y) - 1/d_o]²     if    d(x,y) < d_o
        0                                  if    d(x,y) > d_o
            where:
            d(x,y) = Current distance to obstacle = sqrt(x² + y²)
            d_o=Maximum range of the repulsive force.

The robot's potential function at any point (x,y) is then modeled by the equation:

V(x,y) = V_a(x,y) + V_r(x,y)

where:

V_a = Attractice Potential Function

V_r = Repulsive Potential Function

Algorithm

Using only our potential energy function V(x), we can determine the path which our robot should take through C_free using the following algorithm.

1. Decide upon a quantum: e = Maximum distance traveled in each step. Let k=1.

2. Find the gradient of the potential function = grad(V(x))

3. Let u_k be the direction opposite of the gradient vector. Note: u_k between [0..2pi)

4. let new position (x_k+1,y_k+1) = (x_k+e*cos(u_k),y_k+e*sin(u_k))

5. If (x,y) is within distance D of the goal, declare success.

6. If Q iteration have passed declare failure(indicates local minima is probably present)

7. Goto step 2.