You start a taxi business that operates transportation to the airport. When you show up to the airport each day, you receive a list of passengers that must be brought to the airport. Your taxi has room for two so each trip you can choose to pick up one or two passengers and deliver them back to the airport. The cost of each trip equals the distance traveled (assume you can lookup the distance between the airport and a passenger or between two passengers). You believe you can use graph search to minimize the distance traveled each day.

1. Formulate this problem as a graph search problem.

(a) States:

(b) Initial State:

(c) Actions:

(d) Transition Model:

(e) Goal Test:

(f) Path Cost:

2. Because of its optimality and completeness, A* seems like the natural choice for the search algorithm. Come up with an admissible and consistent heuristic. The trivial heuristic of h(n) = 0 will not receive any points.

3. Something you had not anticipated was passengers cancelling their rides. The original route you calculated at the beginning of the day is no longer optimal, but you believe you can re-plan quickly on the way. How can information from the original route be used to improve the speed during re-planning?

4. Another feature you want to add is the ability to handle premium passengers who are willing to pay extra in order to ride alone. How would including these passengers affect the problem formulation?