In this assignment, a simple differential drive car needs to be controlled in a world filled with walls and open space. In addition to fixed walls, there will be road blocks which may or may not be open. The task is to execute a series of commands that will transition the car across the map to the goal without colliding with either a wall or road block.
We tried three different algorithms: breath first search, A* with back tracking, and policy iteration and reported the advantages.
In policy iteration, we evaluate the space into grids., and then plan based on the cost of certain grid compared to its neighbors to choose the previous step. The cost map considering the uncertainties is:
And the planned trajectories can be seen in the following:
In many situations, the vehicle needs to replan once getting close to the potential road block and making sure if the road is blocked or not. The planned path needs to be regenerated based on the vehicle dynamics. The results from A* with back tracking is faster in large maps and the motion primitives introduced enhances the dynamic feasibility of the trajectories.
Shih-Yun (Laila) Lo 