One was required to write a robot program that enables a robot to explore the arena and produce a map. The arena had a small number of obstacles, placed at random locations. There was a single coloured sheet of paper which the robots had to be able to detect using the colour sensor which also signifed the end location. When finished generating the map, the robot had navigate back to the ending position.


I mostly focused on the A* search task, and also provided the foundation for the LCD Occupancy Grid Display.

Occupancy Grid Display

I looked into the different LCD classes, and played around with TextLCD and GraphicsLCD to understand their differences, and to see when and how they could ‘overlap’ together. Interesting results revealed how one class only allowed to clear entire screen, where as the other allowed the user to clear a specific section by inputting coordinates.

I made the initial grid of rectangles, using the entire screen, by getting the width and height via the getWidth() and getHeight() methods, and diving them by the constant number of grids horizontally and vertically.

Made the foundational for-loops and if-statements to initialise the grid, and display a sample occupancy grid values such as 0 for empty, 1 for obstacle and 2 for final target position. Then added offset to the coordinates so the values would appear in the middle of each rectangle, rather than starting at the top left corner.

Finally, I started experimenting with trying to update the display values in real-time as the robot moved along, and explained to Adam several potential ways to do so before passing on the task and my code entirely to him.

A* Search Algorithm

I fully implemented the entire A* search for the pathfinding by making two classes:

The first, AStarNode, contains the information on the nodes used in the search, such as it’s X and Y coordinates position, it’s parent node, whether it’s an obstacle or not, and methods to calculate the manhattan distance from the current to target position.

The second, AStarSearch, which extends the AStarNode class, has the actual A* algorithm inside a while-loop, and several functions for detecting obstacles, building the best path List, initialising the nodes, searching the occupancy grid matrix for the target position, etc.

The main idea of the search is to divide the nodes into an open and closed list, for which a PriorityQueue and Hash were used instead of standard ArrayLists, as they reduced the time complexity required to re-arrange or check the list by at least a magnitude.

The code was based on available generic A* pseudocode, and the main challenge was conceptualising the conversion from integer values in a 2D array to nodes, and then converting them back in a [i,j] format to be inserted in a returned list.