After talking with professor during the last meeting, I first updated the algorithm so that it can start and end of different nodes. I then embarked on testing the limits of my algorithm.

To do that, I first need to generate maps of my own. I first randomly generate the x and y coordinates of n nodes. The weight(distance) of edge between each pair of nodes is always the euclidean distance. I chose this to be the distance to avoid problems with the heuristic function in A*. After generating the nodes, I generate the edges. In order to test with maps of different sparseness, I only choose to include a certain percentage of all edges. When I include 100% of all edges, then the map is fully connected and these maps are usually the most challenging ones within the same node count.

While testing, I also alter the number of nodes that need to be visited. I do this by randomly marking y% of all nodes to be required nodes. For each map with n nodes and x% sparseness and y% required nodes, I generate 50 different tests. Each test has a randomly generated origin, a randomly generated destination, and a randomly generated list of nodes that need to be visited. After the algorithm runs and finds a optimal route, I check for correctly by checking whether route[0] == origin, route[-1] == destination, and whether all required nodes are in route. I did not perform optimality check.

I tested with map up to 1000 nodes and up to 50% sparseness. I stopped at 50% sparseness because I think it is unfeasible for supermarkets to have a map that is very dense. There does not exist a direct path from the middle of an aisle to the middle of another aisle. My algorithm’s result is correct for all tests. The most computationally intense testing I did was map with 1000 nodes, 50% sparseness, and 50% of all nodes need to be visited. The planning can be done within 40 seconds. One caveat to this is that computing the shortest path between each pair of nodes using A* takes around 30 minutes. However, this is not an issue because my algorithm pre-computes all these information and saves them with the map. When each customer submits their shopping requests, no A* needs to be run.

Overall, I have also been considering the risks, feasibility and ethics of the project.

Next week, I plan on doing additional tests to mitigate risks, and web interface integration to increase our feasibility. Finally for the ethics portion, we want to make sure the goal of the project is not to full replace the current shopping experience, but the enhance it for users who would like to try the Autocart.