#A_star search on package delivery problem: Package delivery companies such as UPS and FedEx route millions of packages every day using thousands of vehicles. How do they decide which package to load, where and when? This is a complex problem with all sorts of constraints such as time, cost and capacity. In this assignment, imagine yourself as the owner of a newly started delivery business. To improve efficiency, you need to build a simple delivery planner. 3.1 Laying the groundwork Before you start delivering packages, you want to get familiar with the basic search algorithms so that you don’t have to worry about those details later on. (1). We have already implemented uniform cost search (UCS) for you. Take a look at the code(see util.py) to familiarize with the algorithm, and try running it on the trivial test case (util.trivialProblem in util.py): import util ucs = util.UniformCostSearch(verbose=3) ucs.solve(util.trivialProblem) This should print out a trace of what the algorithm is doing. Experiment with different graphs and look at the output to get an intuition for the algorithm. Note that UCS might explore many more states than the number of states along the optimal path. Let’s try to quantify this: fill out createUCSTestCase(n) in submission.py. The function takes an integer n as input, and returns a search problem on which UCS explores at least n states whereas the optimal path only takes at most two actions. (2). Recall from class that you can implement A* by an elegant trick: take a problem P and reduce it to another problem Q, such that running A* on P is the same as running UCS on Q. Fill out astarReduction(problem, heuristic) in submission.py. Note that UCS, which is doing all the hard work, has no idea that it’s actually running A*! 3.2 Package delivery Now you can build a package delivery planner by applying the algorithms you developed. Let’s treat those algorithms as black boxes and focus on modeling. You will deliver packages in the following scenario: the city you live in can be viewed as a m ⇥ n grid, where each cell is either free (.) or occupied by a building (#). As you just started, you have only one truck (T). You have k orders, where the i-th order has a pickup location (Pi) and a drop o↵ location (Di). Here’s an example of a scenario: D0. . . . T . # # P1 . . . . # # . . P0. . . . D1 There are 6 actions in total: you can drive the truck around (moving north, south, east, or west), pick up or drop o↵ packages. Finally, you must return to your starting location(make sure you don’t crash into any building during the whole process!). When you enter Pi, you can choose to pick up the i-th package if it hasn’t been picked up. When you enter Di, you can choose to drop o↵ the i-th package if you have picked it up. Moving from one cell to an adjacent cell costs 1 plus the number of packages that are being carried. You want to get all packages delivered and return to starting location, with minimal total cost. (1). Formalize the problem as a search problem, that is, what are the states, actions, costs, initial state, and goal test? Try to find a minimal representation of the states. In addition, how many states are there in your search problem? (express your answer as a function of m, n, and k, also include a brief explanation). (2). Implement the search problem you described by filling out DeliveryProblem in submission.py. You can run uniform cost search on it to solve the sample delivery problems in util.py. If your code is correct, you should be able to run the following: import util, submission ucs = util.UniformCostSearch(verbose=1) scenario = util.deliveryScenario1 ucs.solve(submission.DeliveryProblem(scenario)) scenario.simulate(ucs.actions, True) # Visualize the solution print ucs.numStatesExplored, ’number of states explored.’ (3). Now you have delivered some packages, it’s time to make the search faster (at least in theory). Let’s consider consistent heuristics which correspond to solving a re- laxed problem. The first relaxation is assuming that you can drive through buildings and not deliver any packages, but you still have to go back to starting position. Implement createHeuristic1(scenario) in submission.py by using such relaxation. (Remember a heuristic function takes a state, and returns an estimate of the minimum cost from this state to the goal state) In addition, run A* with your heuristic in util.deliveryScenario1, write down how many states were explored in your writeup. (4). You were perhaps a bit too relaxed, so in this relaxed problem, let’s suppose you have to deliver some given package, and after that you have to go back to starting position - but you can still drive through buildings. Implement createHeuristic2(scenario, package) in submission.py by using such relaxation. In addition, run A* with your heuristic in util.deliveryScenario2, write down how many states were explored in your writeup. (5). In this final relaxation, each time you will deliver the most costly package (recall that the maximum over consistent heuristics is still a consistent heuristic), you can still drive through buildings. Implement createHeuristic3(scenario) in submission.py by using such relaxation. In addition, run A* with your heuristic in util.deliveryScenario3, write down how many states were explored in your writeup.