Laboratory 6 - Path planning (assigned on Feb 20)

Objective

Implement and test a path planning algorithm

Steps

  1. Implement the Search() and MarkCell() procedures.
  2. Create a sample grid, run Search() for a few different maps and a few different start and goal positions, and print the values on the grid.
  3. Implement the Plan() procedure.
  4. Run Plan() on a few different maps and different start and goal positions, and print the resulting path.

Optional parts

  1. Make the robot execute the planned path using fuzzy rules. More precisely: input a grid that corresponds to the actual configuration of obstacles on your table, and use your path tracking procedure from the last lab (with fuzzy rules) to make your robot go to the target position following the planned path. Show in your report the environment that you have used for testing.

  2. Write a function to grow the obstacles in the map by at least one robot radius before you do the planning. Show the resulting map in your report. Also show the results of planning with and without obstacle growing.

  3. Implement Depth First Search, and show the results as above.

  4. Implement Heuristic Search, and show the results as above.

  5. Implement A* Search, and show the results as above.

  6. There are better heuristic search algorithms, for instance IDA* or D*. Try to implement one of them, and report the results.

Report due: Mar 2

Make sure to read the "How to write your lab reports" document.

Include (only) your code, with comments.

Include some printouts of the grid before and after the Search is done, with different maps, start, and goal positions.

If you did any of the optional tasks, describe the results. For task 5, also show in the report the environment used for testing.