Created a taxi dispatcher program to find the optimal route to pick up and drop off a random selection of passengers. This program used various search methods to accomplish this. To implement the this my program created a goal state behind the nodes of the waiting customers. In searching for the customer, the search functions considered the fixed cost of adding and dropping off that passenger. Another search would be used to take the customer to his destination. After that the next customer would be sought out by searching for the goal state until no more customers are left. The taxi then ends there and doesn’t return to anything. So far as performance, I found that the breadth first and uniform cost searches have similar performance. Depth first search found a costlier path that had a greater chance of being significantly costlier as K and N got bigger. For small K and N, all methods were similar in the path cost, number of goal tests done, and states. The depth first search from casual observation seemed to be best at driving down the number of goal test done and actions taken but didn’t seem to be as useful for reducing the number of states.

Code