This project involved implementing an algorithm to direct a robot through a warehouse in order to pick up boxes and deliver them to a dropzone.

To prevent a sheer brute forcing method, this has to be done within a certain 'cost'; each movement the robot makes (moving up/down/left/right/diagonally as well as lifting/dropping boxes) comes with a cost. Illegal moves (such as directing the robot to move through a wall) come with a steep penalty.

I used the A* algorithm to help with this - A* is a graph traversal and path search algorithm which uses a heuristic to guide its search. In my case, I used the Manhattan distance to serve as a heuristic, however there are many other options for this (eg. Euclidean distance).

Figure 1 is simple visualization of Manhattan distance.

The purple asterisk represents the goal, and the blue numbers in each grid cell are the number of steps required to reach the goal from that grid cell.

The formula looks like this (g is the goal):

$m(x,y) = |x - g_x| + |y - g_y|$

Note: this assumes that only standard (up/down/left/right) moves are being used and not diagonal ones, so there is room for error. I decided to stick with it since it's a simpler implementation 😅 .

Figure 1: Example of the Manhattan distance

A* uses this heuristic, as well as the movement costs, in order to determine the lowest cost series of actions from the starting node to the goal.

Figure 2: Warehouse Search

Figure 2: Warehouse Search

Figure 2 shows the A* algorithm in action. The robot is directed towards the boxes (in order of their number).