Project 3: Un Chance to Save the World (Due April 29)
Kim Jong Un continues to threaten to launch nuclear missiles, an act which would endanger several fish in the western Pacific ocean. An operation has been called for to mitigate this risk.
Before a team can enter and sabotage the nuclear facility, the security cameras need to be turned off by somebody or something visiting each camera control panel (which look remarkably like APRIL Tags). The security building is protected with a weight-responsive alarm; if anybody or anything drives over protected regions of the room, the alarm will sound. Every night, the regions which are armed are changed; for the ease of personnel, a path is preserved to allow them to visit each of the camera control panels.
A person would certainly be noticed, so it has been decided to send in the next generation of top-secret drones. This drone needs to visit each control panel, as quickly as possible, without straying from the allowed paths.
Fortunately, we have been able to crack the DPRK's cyber systems in order to download the allowed path plans for the evening of April 29.
The Assignment
A preamble: some files to help you can be downloaded here. You should read through and understand what I've given you before you start coding. This project has two steps.
Step 1 - Calculate the shortest path (80/100 pts): Your program should read in a text file detailing which paths between landmarks are allowed by the security system. Three such files are in the tarball you downloaded, as canDrive*.txt. You'll notice in each one a 2D block of 1s and 0s. On the i-th row and the j-th column will be a 1 if it is legal to drive from the i-th landmark to the j-th, and a 0 if it is not. Given this information, and which landmark the robot has been started on, display the order of landmarks to be visited:
taylor@albert:~/Test/UnChance$ python pathPlan.py canDrive.txt starting id? 4 [4, 0, 1, 0, 3, 0, 2]
Do this using A* search.
Step 2 - Perform the task with your robot (100/100 pts):
To get the rest of the credit, your robot should actually drive the route you calculated. To do this, it would first spin in circles to localize itself, and then drive to a point just in front of each landmark. It should do this without any additional input from you.
Our maps don't start with a landmark with id 0. If the smallest landmark in your map is 2, you should add 2 to every element of the array printed out by part 1.