Carnegie Mellon University

The Robotics Institute.

Robotic  Motion Planning, 16735: Homework 4

A*  in R² × S configuration space

 

Movies:

 

Success 1    Failure 1

 

Note: The green dots in the movie indicate the elements that have been in the open set.

 

 

 

 

 

 

 

 

 

 

 

 

 

Robot Model:

The robot is  Omni directional and can only turn in place. I have used a 10 point connectivity, 8 in the plane along R² and 2 nodes above and below the current configuration along S.

 

Algorithm:

 1. Pop the node with the highest priority in the open list, add this node to the closed list.

 2. If the popped node is the goal exit

 3. Include all the neighbors of the popped node (not in the closed list) in the open list defined by the      connectivity.

 4. If the open list contains no element exit with failure.

 

The heuristic function used is the Euclidean distance between the node configuration (C) and the goal configuration (C_g) = √(C-C_g).  The Euclidean norm made most physical sense to me and therefore I used it, although it may not be the most efficient heuristic to use.

 

Notes:

1.The obstacles in the configuration space have an assumed shape. The shape does not correspond to   the real obstacle unless the robot is circular.

2. The cost function from one node to the neighboring node is proportional to the Euclidean distance between them. The scaling of the cost to the E. distance is the same along R² and S