CSE 597 F : Intelligent Robotics 
Lectures 3 & 4 : Sep 09 & Sep 14
 
Topics Covered 
 
 
Basic Motion Planning Problem - Configuration Space Formulation :
The basic idea is to represent a robot as a point in a space (called the configuration space) and to map the obstacles in this space.  This mapping transforms the problem of planning the motion of a dimensioned object into the problem of planning the motion of a point.  The motion planning problem thus becomes defining a set of configurations from the initial state to the goal state in the free space. 

Assumptions : 

  • Robot is the only moving object in the workspace 
  • Ignore the dynamic properties of the robot
  • The robot is a single rigid object, ie. an object whose points are fixed with respect to each other
Problem Definition : 

    Let A be the robot (rigid object) moving in a Euclidean space W (called workspace), represented RN, with N = 2 or 3 (depending on dimension - 2d or 3d).  
  
    Let FW be the world co-ordinate system embedded in the workspace W (fixed frame). 
    Let FA be the cartesian frame embedded in the robot A (which means every point of A has a fixed position with respect to FA) (moving frame).  

    Let q be the configuration of the Robot A.  q of A is thus a specification of position T and orientation 0 of FA with respect to FW. 
  
    Let C be the configuration space which defines all possible positions and orientations a robot can be in W.  Thus A(q) is a subset of W occupied by A at configuration q. 

    Let B1, ... , Bi be fixed rigid objects distributed in W, called obstacles. 
  
    Let us assume that the geometry of A, B1, ..., Bi and the locations of B's in W are accurately known. 

The problem can be defined thus; 
"Given an initial position and orientation and a goal position and orientation of A in W, generate a path T 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." [Latombe] 

[ Go Top ] 
 
Planning Approaches : 
  • Roadmap Methods
      • The Roadmap approach to path planning consists of capturing the connectivity of the robot's free space in a network of one-dimensional curves, called the roadmap, lying in the free space Cfree.
       
  • Cell Decomposition Methods
      • This approach consists of decomposing the robot's free space into simple regions, called cells, such that a path between any two configurations in a cell can be generated.  The cells must either be disjoint or meet precisely at a common face, edge or vertex.  
       
  • Potential Field Methods
      • This method consists of setting up a potential field in the space with attraction (or +ve charge) towards the goal and repulsion (-ve charge) towards the obstacle.  The goal is reached by following the steepest gradient of the potential field.
[ Go Top ] 
 
Roadmap Methods : 
Visibility Graph : 
The basic algorithm : 
1.  Construct the visibility Graph G. 
2.  Search G for a path from qinit to qgoal (initial and goal configurations) 
3.  If path is found, return it ; otherwise, indicate failure
Construction of the Visibility Graph (a naive algorithm):  
  • The vertices of the obstacles are considered as nodes.
  • The nodes are linked with straight line segments if they do not intersect the interior of the C-obstacle region.
  • The initial and the goal configurations qinit and qgoal are considered as nodes and are linked with straight line segments to other nodes, if the line exists in Cfree.
This algorithm given above, requires time O(n3) where n is the total number of vertices of CB.  More efficient algorithms performing in time O(n2log n), O(n2) and O(k + n log n) [where k is number of edges in G - worst case k is in O(n2); in better cases, as small as O(n)] have been proposed.  

[To find references for algorithms refer Latombe, pg 157] 

Searching G for a path : 

Searching G can be done using various graph searching techniques.  Whenever a path exists, it is returned; otherwise, a failure is reported.  The search is done in time O(n2)  or O(k log n) depending on the search technique.  [Refer Latombe, pg 157 for reference to algorithms] 

[ Go Top ] 
 
Voronoi Graph :
The Voronoi graph gives the network of paths as far away from the obstacle as possible.  Hence it tends to maximise the clearance between the robot and the obstacles.  When C-Obstacles are polygons, the voronoi diagram consists of straight and parabolic segments (eg. between two lines - V graph is a straight line ; between two points - V graph is a straight line; between a point and a line - V graph is a parabolic segment). 

Construction : 

  • Choose a point closest to two obstacles
  • Connect the points with straight line segments (closest to two edges or two vertices) or parabolic arcs (closest to a pair consisting of an edge and a vertex) to get the voronoi graph
  • Connect the qinitial and qgoal to the graph using straight line segment.
Complexity : 

Let n be the number of vertices. 
A naive algorith constructs the Voronoi diagram of Cfree in O(n4) time by considering the O(n2) pairs (edge, edge), (vertex, edge), (vertex, vertex) and computing the intersections of corresponding equidistant curves.  There are algorithms which compute in O(n2), O(n log2 n) and in optimal O(n log n) time. 
 

[ Go Top ] 
 
Randomized Roadmap :
The Randomized roadmaps are used when the dimension of Cfree is high.  

Construction : 

  • Pick points randomly in configuration space and reject it if it is not in Cfree
  • Call the points milestones and connect them if distance between 2 points is less than D (max connect distance) and straight line connecting the points lie in Cfree
  • Avoid forming cycles by not connecting two lines emerging from the same milestone.
[ Go Top ]