We have made progress in different aspects of our project. We have continued with our Raspberry Pi configuration, made good progress in defining and solving our multiple travelling salesman problem (mTSP), made an initial design for our MATLAB GUI, and started working on our robot control.
Raspberry Pi Configuration
This is a continuation to what we have shown in Update #2.
We set up our ROS MASTER on a standalone Linux laptop by installing:
We set up our Raspberry Pi by installing:
Multiple Travelling Salesman Problem
The mTSP has several variations depending on the application at hand. In our case, we have the following specifications:
- Any store can be assigned to any robot.
- There is no specific order in which stores need to be sanitized, as long as they all belong to the same wave of user requests.
- The total time taken for all stores to be visited and sanitized should be minimum. This means that we need to minimize the time of the longest route assigned to a robot, sometimes referred to as Min-Max mTSP.
- Robots do not have certain depots. For each wave of sanitization requests, robots start their route from the location of the last store they sanitized from the previous wave, and end it at the location of the last store assigned to them from the current wave.
We also base our initial model on the following assumptions:
- The speeds of all robots are equal and are chosen to be a certain constant at all times.
- Robots are treated like point masses. The time taken by robots to appropriately change their heading before travelling to the next allocated store is not taken into consideration.
- The time taken by a robot to go from one store to another is the time it takes to travel the shortest distance between those two stores at the robot’s fixed speed.
- For each of the mall stores, the time needed for complete sanitization depends on the size of the store and hence is constant at all times.
We opted for using a genetic algorithm in solving our mTSP. We adapt Elad Kivelevitch’s MDMTSPV_GA which solves a multiple-depot mTSP using the genetic algorithm. We introduce the following adjustments:
- 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). –> in progress
Figure 1 shows our initial results including the first two adjustments. We simulated our 5 stores with locations (-2, 2), (0, 2), (2, 2), (-1, 0) and (1, 0). The blue robot is starting from the (-2, 2) store (store 1) and the red robot is starting from the (1, 0) store (store 5), which resemble the stores lastly sanitized by each robot respectively. The best routes found by the algorithm are:
Blue Robot: Store 1 –> Store 2 –> Store 3
Red Robot: Store 5 –> Store 4
(a) Best routes for red and blue robots.
(b) History (across iterations) of the minimum distance of longest tour.
Figure 1: 5 Stores, 2 Robots
Because the simulated number of stores and robots are very small, the algorithm actually converges after only 5 iterations (in the run shown in figure 1). We then simulate a case where there are 20 stores and 5 robots. The algorithm takes 2790 iterations to converge to a near optimal solution. Figure 2 shows our results for this run.
(a) Updates of best routes of robots at every iteration of the algorithm.
(b) History (across iterations) of the minimum distance of longest tour.
Figure 2: 20 Stores, 5 Robots
MATLAB GUI
We have made an initial design for our user interface, shown in figure 3. In the top left panel, the user can select the stores that they wish to sanitize. In the top right panel, the stores assigned to each robot will be displayed with the corresponding estimated time of arrival. This way, the user can keep track of the status of the whole system and be aware of the waiting time of each store. In the bottom panel, the positions of our two robots will be plotted in real-time. This provides the user with even better visualization.
Figure 3: Initial design of our MATLAB GUI.
Robot Control
We started working on a pure pursuit controller for our robots. We are currently able to update the positions of our robots based on measurements from our motion capture system. We still need to tune the lookahead distance and linear velocity for accurate control.
Multi-Agent Robot System for Mall Sanitization 