This week, I first addressed the problem with local re-planning. I was thinking if an obstacle were to appear in the optimal route between Node1 and Node2, I can simple recall the saved shortest path between Node1 and Node2 that has been pre-planned to “go around” the obstacle. But I soon realized that due to the way my algorithm is set up, every pair of adjacent nodes in the optimal route are neighbors. This leads to a problem that if an obstacle were to appear between Node1 and Node2, that obstacle is very likely to be on the pre-computed shortest path from Node1 to Node2. This is simply due to the fact that the shortest path between two neighbors is highly likely just going directly from one neighbor to the other. As a result, when re-planning, I update the map first by removing the edge that the obstacle is on and re-run A* on Node1 and Node2. This way, the obstacle is circumvented in the locally optimal way. After the obstacle is circumvented, the cart will resume its route after Node2. After re-running A*, I put back the removed edge. Running one A* is very cheap, so if the user encounters the same obstacle again, it does not hurt to run the A* again on Node1 and Node2. I put back the edge because I think it is reasonable to assume all obstacles are temporary; removing an edge permanently might reduce the optimality of potential later re-planning.

The above re-planning algorithm overlooks the possibility that the re-planned path from Node1 to Node2 visited some of the other required nodes. If this is the case, local optimality is surely undermined because of redundancy. However, I purposefully chose to overlook this probability because in order to still guarantee global optimality, I need to re-run the entire path planning algorithm on every required node after Node2. In worst case, this can take much longer than a A*. I do not think this trade off is worth it.

For the rest of the time, I focused on testing the robustness of my algorithm. While testing the robustness, I also recorded the average run time across many cases. I already explained how I stress test my algorithm in my last report. I stress tested with map from 100 nodes to 1000 nodes with 100 nodes increment, edge density from 10% to 50% with 10% increment, and 5% to 50% of map nodes being required nodes with 5% increment. All these data will be compiled into graph and included in the final report.

I also worked with Zeyi to create a simulation of the shopping process with the help of the user interface he is working on. I packaged my code cleanly so that the user interface only needs to call two functions find_best_route(origin, destination, requiredNodes) and replan(node1, node2).