A* Search for robot planning and navigation

Overview

This project was done as a homework assignment for CS/ME 469 ML and AI for Robotics at Northwestern. The task was to implement A* search from scratch to enable a wheeled mobile robot to navigate a gridworld with obstacles. Code is not provided since this is a regular homework assignment.

The grid world environment

Two gridworld environments of different discretization coarseness were built and used for testing.

Planning with A*

Results from planning in the coarse gridworld are shown:

Results from planning in the fine gridworld are shown:

Driving planned paths

A feedforward + feedback controller was built to simulate a differential drive robot driving the planned paths. Here is an example of the driven paths:

Online planning

Planning-while-driving was tested. In the previous section, paths were pre-computed, after which the simulated robot would traverse the path. In this section, the robot takes a step and needs to re-plan based on the actual step that it has taken, since the robot controller might drive the robot into cells which are not a part of the planned path. Here are some results: