Exact Cell Decomposition

Overview :

To decompose the robots free space C_free into a collection of non-overlapping regions, called cells such that the union of all the cells exactly equals the free space, C-Space.

Desired Charecterestics:

· Geometry of the cells should be simple enough so that it is easy to compute a path between any two configurations of the cell.

· It should be easy to test the adjacency of two cells, i.e. whether they share a common boundary.

· It should be easy to find a path crossing the portion of the boundary of two adjacent cells.

The cell boundaries are the critical regions in C, i.e, significant changes occur when the boundary is crossed. However no such criticalities in C occur for points within the cell.

Drawbacks of Exact Cell Decompostion

· The primary difficulty is in the decomposition of C-free to cells.

· Simple sweep-line methods exists for simple cases like when C=R² , CB is a polygonal region , but it is harder with both translation and rotation.

Exact Cell Decomposition for C= R²

Assumptions :

· The robot A and all the obstacles B_i’s are polygonal

· C-free is bounded

Definitions :

A convex polygonal decomposition K of C-free is a finite collection of convex polygons , called cells, such that the interiors of any two cells do not intersect and the union of al the cells is exactly C-free.

Two cells K, K^’ are adjacent iff K ∩ K^’ is a line segment of non-zero length.

The connectivity graph associated with a conves polygonal decomposition K of C-free is an undirected graph G where

· nodes in G correspond to cells in K

· nodes connected by edge in G iff corresponding cells adjacent in K

Path Planning with a Convex Polygonal Decomposition

Input : configurations q_init and q_goal, and CB, which has to be a polygonal region

Output : a path in C-free connecting q_init and q_goal

1. Build K, the convex polygonal decomposition of CB.

2. Construct the connectivity graph G of K.

3. Locate the cells k_init and k_goal in K containing q_init and q_goal .

4. Find a path in G between the nodes corresponding to k_init and k_goal –corresponds to a sequence of cells forming a channel in C-free.

5. Find a free path from q_init to q_goal in the channel.

Getting a path from a channel

Let k₁,k₂,….,k_p denote the channel in C-free, where k₁ = k_init and k_p = k_goal

Goal : find a path ( 1-dimentional curve) from q_init to q_goal that is contained in the interior of the channel.

Solution : Use midpoints of cell boundaries as crossing points between cells.

Let Q_i denote the midpoint of the line segment common to both k_i and k_i+1 in the channel, i.e., Q_i is the midpoint of k_i ∩ k_i+1

Then q_init, Q₁,Q₂,…,Q_p-1,q_goal is a path in the channel.

Building K – Trapezoidal Decomposition

Basic Idea : at every vertex of CB, extend a vertical line up and down in C-free until it touches a C-obstacle or the boundary of C-free.

SweepLine Algorithm : Build Trapezoidal Decomposition

Input : boundary representation of CB

Output : trapezoidal decomposition of CB

1. sort the vertices of CB by x-coordinates

2. ‘sweep’ a vertical line L from left to right, stopping at each vertex v in CB.

Exact Decomposition for moving a ladder in a plane

The robot A is a line segment of length (called a ladder) which can translate and rotate in a plane.

The workspace W=R² , and obstacles are polygons and so B is a polygon region

The configuration space C=R² x [0,2∏)

The Critical curve method of Schwartz and Sharir

· decompose the set of positions of P(the x-y plane corresponding to positions of A’s origin into two-decomposition non-critical regions

· the structure of the C-obstacles is ‘constant’ in the θ direction above a non-critical region, i.e. the set of C-surfaces intersected by a line perpendicular to x-y plane does not change .

· boundaries of non-critical regions in the x-y plane are critical curves

· ‘lift’ 2d non-critical regions into 3d cells (cylinders)

· compute the adjacency relationships between the cells (connectivity graph)

Properties of critical curves

· critical curves partition the x-y plane into non-critical regions

· within each non-critical region, a line perpendicular to the x-y plane intersects the same set of C-surfaces

· at a critical curve, the set of C-surfaces intersected by a line perpendicular to the x-y plane changes

· within a non-critical region, the value of θ determines the allowed configurations

Critical curves for a Ladder

· Type-A surface : segment PQ contains an obstacle vertex

· Type-B surface : P or Q is contained in an obstacle edge

The critical curves are projections onto the x-y plane of the following curves in R² x [0,2∏)

1. projections of curves that bound C-obstacle faces (i.e., C-obstacle edges)

2. projections of curves in C-obstacle faces where the tangent plane to the face is perpendicular to the x-y plane

Methods to find critical curves

· compute a boundary representation of CB, project all the edges onto the x-y plane, and find all faces with tangent planes perpendicular to the x-y plane and project the curves in these faces to the x-y plane

· construct the critical curves by working directly with the obstacles in W , i.e., consider all possible contacts

Exact Decomposition of C_free

· Partition cylinders into cells

Definition :

· F(x,y) is the set of all free orientations of PQ when P is at a non-critical position (x,y), i.e.,

F(x,y) = { θ | (x,y,θ) ε C_free }

If all orientations of PQ at position (x,y) are free, then F(x,y) =[0,2∏) .

· A stop is the vertex or edge of B that PQ contacts at the limiting orientations in an interval in F(x,y). Each interval in F(x,y) has two stops – a clockwise stop and a counterclockwise stop.

· ₁(x,y,s) is the value of θ where PQ contacts clockwise stop s with P in position (x,y). ₂(x,y,s^’) is the value of θ for counterclockwise stop s^’

· σ(x,y) is the set of all pairs of stops associated with intervals in F(x,y). If F(x,y) = [0,2∏), then σ(x,y) =[Ω,Ω].

· Let R be a non-critical region, and let (x,y) and (x^’,y^’) be any two positions in R. Then the intervals in F(x,y) and F(x^’,y^’) have the same set of stops, i.e., σ(x,y)=σ(x^’,y^’). Let σ(R) denote this set of stops.

· Let R be a non-critical region, and let [s₁,s₂] ε σ(R).

(R,s₁,s₂) = { (x,y,θ) | (x,y) ε R and θ ε (₁(x,y,s₁),₂(x,y,s₂)) } is called a cell, i.e., cell(R, s₁,s₂) is the set of all points in the ‘cylinder’ above R such that PQ is oriented between the two stops s₁ and s₂. It is a open connected subset of C_free.

Building a connectivity graph

Definition : cells cell(R,s₁,s₂) and cell(R,s₁^’,s₂^’) are adjacent iff

(i) the boundaries of R and R’ ,R and R^’ share a critical curve segment β , and

(ii) (x,y) ε int(β),

(₁(x,y,s₁),₂(x,y,s₂)) ∩ (₁(x,y,s₁^’),₂(x,y,s₂^’)) 0

Thus if two cells k and k^’ are adjacent, then any configuration in k can be connected to any configuration in k^’ by a free path whose projection onto the x-y plane crosses β transversely, with a constant orientation is some neighborhood of the crossing point.

Computing adjacent cells

Let R and R^’ be two non-critical regions such that β is a critical curve section common to the boundaries of both R and R^’ .

An exclusive case analysis would show that whenever int(β) is crossed transversely the set σ(x,y) changes in one of thew following ways

· one new pair of stops appears in σ(x,y)

· one old pair of stops disappears from σ(x,y)

· one of the stops in a pair [s₁,s₂] currently in σ(x,y) changes, i.e., [s₁,s₂] is replaced by [s₁^’,s₂^’] and either s₁=s₁^’ or s₂=s₂^’

Crossing rule for β

1. for each [s₁,s₂] ε σ(R) ∩ σ(R^’),

cell(R,s₁,s₂) is adjacent to cell(R^’,s₁,s₂)

2. for each [s₁,s₂] =σ(R) – σ(R^’) and [s₁^’,s₂^’] =σ(R^’) – σ(R) (if they exist), cell(R,s₁,s₂) is adjacent to cell(R^’,s₁^’,s₂^’).

In this case, one of the following conditions hold :

(a) s₁ = s₁^’ , or

(b) s₂ = s₂^’ , or

(c) s₁ = s₂ = Ω or s₁^’ = s₂^’ = Ω

The connectivity graph and motion planning

Definition : The connectivity graph corresponds to the exact decomposition of C_free into cells is an undirected graph in which

· nodes corresponds to cells(R, s₁,s₂), where R is a non-critical region and [s₁,s₂] ε σ(R)

· two nodes are connected by an edge iff their corresponding cells are adjacent.

Motion Planning

1. enumerate all the critical curves

2. compute their arrangements

3. find the non-critical regions and their stops

4. determine the cell adjacencies

5. locate the cells containing q_init and q_goal

6. find a path in G between the nodes corresponding to the cells containing q_init and q_goal