Algorithm

Overview

The objective of the Algorithm module in the Project is to function as a brain for the robotic system to autonomously explore the maze without hitting any obstacle or wall and plan the fastest route to the endpoint while passing through a predetermined way point.

It processes the sensor values and simulates the movement of the real robot, as well as provides a visual representation of the robot and the maze environment.

Main Objectives

• Design a functional Graphical User Interface for the Simulator Application
• Implement Java Socket connection with Raspberry Pi for transmitting and receiving signals from Android Application
• Design and implement strategy for Maze Exploration
• Design and implement strategy for Fastest Path from X to Y
• Design and implement strategy for identifying the locations and identifiers of the 5 images in maze

Main Tools

• Eclipse
• JetBrain Intellij
• Windows 10 Computer

Functionalities and its Implementations

The simulator allows the user to see the robot moving on the screen while exploring and moving along the fastest path. It also allows sample arenas to be loaded by the user for testing purposes and can be created by editing/creating the ‘txt’ files. The MDF String of the map perceived by the Robot is also displayable on the screen.

Implementation of the Simulator

The User Interface is created using Java Swing library. In the simulator, the SimulatorRobot class (extends from the Robot class) controls the movement of the robot image and update the explored grid onto the screen accordingly.

In the AddJButtonListener class (implements ActionListener), it contains all the buttons added that are displayed on the screen and an instance of the SimulatorRobot. The function to load a map from its ‘txt’ file in the sample arena directory is also included in this class. This loaded map is then stored into the SimulatorSensor (extends from the Sensor class).

The SimulatorRobot class stores an instance of the SimulatorSensor which contains the simulated map. The SimulatorSensor will return the sensor values to the SimulatorRobot to update the Map and SimulatorMap.

The Map class sets the grid of the perceived map by the Robot class and it also creates the MDF String. The SimulatorMap controls the grid display of the map on the screen.

During Maze Exploration and Fastest Path Simulation, their respective Thread classes take in the instance of the SimulatorRobot class to control the robot’s movement and maps it onto the screen. These are further explained in Section 3 Maze Exploration and Section 6 Fastest Path respectively.

During the real run, the Java Application establishes its connection with RPi via the Java Socket connection. The Java Application reads the IP Address and the Port Number of the socket in the Constant.java, and both software are to connect with the same WIFI for the connection to be successful.

To begin Maze Exploration, the Android has to notify RPi, and RPi will then send the exploration message to the Java Application. Upon receiving the message, the Java Program will send relevant messages to command the Arduino to sense, move, etc. For each command sent to Arduino, the Arduino will send the sensor values to the Java Application to acknowledge the completion of the command. This protocol reduces the message exchange which is the bottle neck of the run.

To begin Fastest Path Through a Way Point, the Android also has to notify RPi, and RPi will send the fastest path message to Java Application. Upon receiving the message, the Java Program will concatenate the command message and send it as a singular message since the path can already be fully determined based on the map generated from exploration.

For Image Recognition, the communication is similar to normal exploration with the additional commands for RPi to take photos.

Implementation of Communication with Raspberry Pi (RPi)

The ConnectionSocket class is in charge of connecting to the RPi. It also sends messages via bytes and converts the received bytes message into string.

For every sense/move request sent from the RealRobot class, it will run the acknowledge function above to accept the sensor values and stores them with the position (x, y) and direction which the sensor readings are for.

In the Fastest Path, message commands are chained together separated by ‘|’ symbol. One example is “W12|A|W17|”.

The algorithm we have chosen to adopt is the wall follower method. Taking into account that we have 2 short range sensors on the right side of the robot compared to the 1 far sensor on the left, we have chosen to hug the right wall. The robot will first explore the maze by hugging the right wall until it returns to the start point.

If any grid is left unexplored after completing one round, the algorithm will keep searching for the fastest path to the nearest unexplored grid until the arena is fully explored. It will then find the fastest path back to the start point to conclude the exploration phase. 

Due to the two motors having a speed difference, it is impossible to ensure 0% error during the run. As such, realignment is extremely important to ensure we achieve an accurate map of the arena. This is done both by hardware and by software.

At every corner, the software will call corner calibration as it is the most accurate calibration that the Arduino team has implemented. However, throughout the entire Maze Exploration, there is also auto-realignment implemented inside the Arduino (hardware). The robot will utilize the sensor readings as inputs, automatically realigning itself based on its relative position in the 3×3 area, ensuring straight and accurate movements.

As hardware is not 100% reliable, the sensor values are not accurate all the time. They tend to be extremely inaccurate when the robot is too far for the short sensors or too close for the far sensor. We assume that the far sensor is always slightly less accurate than the short sensors.The label and the distance of the grid are stored in the Map class, where label denotes the type of the grid and distance denotes the number of grids away from the grid that is being updated.

To eliminate phantom blocks, we exercise a weighted strategy to prioritize the sensor readings that are more reliable. Readings which have been taken closer to the targeted grid will have priority over readings which have been taken from a further distance. We have also chosen to prioritize our short range sensors as they have proven to be more accurate than our far sensor. This is done by adding a penalty of +2 to the far sensor readings. Lastly, when a grid is walked over by the robot, it will be marked as explored with no obstacle and no other reading will be able to overwrite it. 

We have chosen to follow the well-known A* algorithm to calculate fastest path. Since turning takes up the most time in comparison to moving straight, when a turn is required, it incurs an additional penalty as compared to moving straight. This is to ensure that the fastest path computed takes the least number of turns possible.

During the fastest path through a way point, the algorithm computes the fastest path to the way point from the start and then the path to the end point from the way point. After which, they concatenated and sent to Arduino as one message in order to reduce communication time.

For Image Recognition, one of the concerns we faced was the additional time needed for Image Capturing on the Raspberry-Pi, which might exceed the 6 minute time limit. To handle this problem, the algorithm will only request for an image to be taken of the obstacles when it cannot guarantee another opportunity in the future and if it has not already been taken. 

To make this Java Application simple to use, all the configurable components are stored under Constant class under the Config package.
Items are icons, grid image, robot image, image_rec, exchanged message etc.

For the ease of use, the application will always prompt the user if necessary, and display response for every user action. There will be pop up selections to choose what functions the user would like to be able to see. The pop ups are displayed below:

Checking for Real Run	Printing for Debug Text File	Checking for the Display of Simulator