Motion Planning HW #1

Due : Aug/29/2007

1. Download a software package, develop your own, use one that you have to draw some obstacles, selects two points, and draws a line between them.

   I had downloaded all package of MPK and simulated with demo files.   I made motion planning tool using Matlab. This graphical interfaced solution established by GUIDE is shown below. It contains graphical board and several buttons to control all motion of objects. First of all, user can set shape of obstacles using mouse (left click to set vertices) and also locate Start/Goal Position as well as orientation. Since graphical board is 2D, user has 3 degree of freedom(x, y, theta). Thus, either start or goal position can be described by position and orientation. Secondly, after setting all obstacles and start/goal postion, then user can select algorithm of path planning. Now we have straight path plan from start position to goal postion, so if we press "Path Planning" button, we might have straight line from start to goal. Planned trajectory appears with red dashed line. Finally, user presses "Animate", then simulation can be done.  



   If user want different motion planning algorithm, all he has to do is to make matlab function and put in list.  Unfortunately, simulation which object follows planned path is not prepared yet. However, simulation capture of uncomplished version is below.

2. Develop a simple, yet complete, path planning algorithm and be prepared to "implement" it on a person in Wedneday's class.

   - Assumption   

1. Object can memorize where it passed by.  

2. Object can smell(?) goal position which means object know approximately where the goal is. 

- Idea  

I am inspired by fairy tale, Hansel and Gretel, and also by fluid flow on sink or magnetic field theory. In the fairy tale, Hansel and Gretel, they find their house using the bread they dropped before. In contrast, I would like to avoid way I have passed by. Like potential function, if I rank the way I have passed by before as high and also obstacle, then I might be able to construct almost continous potential field. And then I might make object to move lowest direction(divergence of potential function). Iteration of this process may take object to goal.

(1) Go direction to smell (goal)

(2) Memorize way object passed by and map it high potential.

(3) Since obstacle is high potential part, find lowest potential direction.

(4) GoTo (1)

Actually I am not sure this algorithm will lead fancy trajectory because in unfortunate case, object has to track every floor except obstacle. However, since this algorithm avoid every path it has taken, it proves not to fall in infinite loop and fail to accomplish missions. I think this algorithm might be typically efficient at large space with a lot of obstacles.