Update #4: Robot Control, mTSP & GUI

We have continued our work on the different modules of our project. We further developed our genetic algorithm for solving the multiple travelling salesman problem (mTSP), integrated it with our MATLAB GUI, and finished working on our robot control.

Robot Control

We intended to use a pure pursuit controller to move the robot towards its desired goal. However, since it needs a pre-calculated path (waypoints) towards each of the desired goals, we instead decided to use a proportional controller to control the robot heading and linear velocity. We computed the robot’s heading using the information provided by our motion capture system. It reports the orientation of the robot in quaternion notation, and we then used MATLAB’s quat2eul function to get the robots’ yaw (heading). As shown in figure 1, the robot is now able to move towards its desired goal (the white box) representing one of the stores.

Figure 1: Robot navigating to its desired goal (white box = one of the stores).

For each of the robots, we also developed a standalone function that takes as input desired store numbers representing sequential goals that the robot needs to navigate to. As soon as the robot arrives at its first goal, it is prompted to navigate to the next and so on.

Multiple Travelling Salesman Problem

As explained in our previous update, we are building on Elad Kivelevitch’s MDMTSPV_GA which solves a multiple-depot mTSP using a genetic algorithm (GA). The initial adjustments we decided to make (and are currently done with) were:

• The robot does not return to a certain depot after it is done with visiting the stores assigned to it. –> done
• The depot from which each robot starts its route is mapped to being the location of the store it last visited. –> done
• We minimize the time, as opposed to distance, of the longest route assigned to a robot (taking into account the time needed for store sanitizations). –> done

We then spent more time analyzing the implementation of the GA itself and how we can improve it. The GA is a parametric algorithm; its performance is highly dependent on how those parameters are chosen. Two very important parameters of any GA are the crossover and mutation rates (CR and MR respectively). While crossover (exchanging genes between individuals of the population) helps the algorithm converge to better solutions, mutation (introducing random changes to individuals of the population) allows for diversity in the population and reduces the chance of getting stuck in local optima. Since Kivelevitch’s MDMTSPV_GA only applied mutation (CR ~ 0, MR ~1), we are working on introducing crossovers in the algorithm and appropriately balancing between them. Instead of using preset CR and MR based on parameter tuning, we will be appropriately changing them during run-time using Hassanat et al.‘s methods of deterministic parameter control: dynamic Decreasing of High Mutation ratio/dynamic Increasing of Low Crossover ratio (DHM/ILC) & Dynamic Increasing of Low Mutation/Dynamic Decreasing of High Crossover (ILM/DHC).

MATLAB GUI

Having our initial design, we started working on the implementation of our MATLAB GUI.

• We added a function that will draw our robots in real-time on the plot (as shown in figure 2).

Figure 2: Running MATLAB GUI. Robots are in their starting positions and no stores are initially assigned to any of the robots.

• For a certain time window, the user is now able to select the stores to sanitize. The Sanitization Requests panel is then disabled as shown in figure 3 and remains disabled until the whole sanitization process of the chosen stores is finished.

Figure 3: Running MATLAB GUI. By the end of the time window allocated for user requests, the Sanitization Requests panel is disabled and the selected stores are assigned to the robots then shown on the Tracking panel.

• The stores chosen by the user for sanitization are sent to our algorithm solving the mTSP which determines the stores assigned to each robot. These assigned stores are then displayed on the tracking panel (still working on the ETA) as also shown in figure 3.
• The whole process repeats giving the user another time window to issue requests.

Now that our MATLAB GUI is integrated with our algorithm for solving the mTSP and the whole workflow is outlined, what remains is to integrate the GUI with the actual hardware while it is executing in real-time.