Project 1
Artificial Intelligence
CSCE 5210 – Fall 2021
Distributed: Tuesday, August 31
Due: Tuesday September 21
[Solutions to this assignment must be submitted via CANVAS prior to midnight on the due date. Submissions up to one day late will be penalized 10% and a further 10% will be applied for the next day late. Submissions will not be accepted if more than two days later than the due date.]
This project is to be undertaken in pairs. No individual work please. Please state the names of the two people undertaking the project and the contributions that each has made. Only ONE submission should be made per group.
Purpose: To gain a thorough understanding of the working of a simple, table-driven agent. This will enable you to put into practice the concepts of performance measurement, environment interaction, and the use of actuators (PEAS) to assist the agent’s navigation in a stochastic setting that mimics a real-world environment. Thus, this requires reading through the project specification carefully to make sure that you understand its requirements. Jot down any questions/doubts that you may have and feel free to ask me questions in class or in person. Together with your partner, work out a strategy before you start coding the solution in Python. Given the limited timeframe for the project, some simplifications have been assumed. In all cases, when simplifications are used, they have been pointed out explicitly. You may find it useful to compile: a) a list of all functional requirements and b) a list of all assumptions before starting to code.
Environment Description: The application is a ridesharing one to be deployed in any given area of geographical coverage spanning a city. The environment is specified in the form of a graph structure as represented below. Each node in the graph represents both a potential pickup/drop-off point. The distance between a pair of connected nodes is represented by the numerical value on the edge connecting the nodes. The value represents the distance in miles.
The ABC company employs a fleet of N vehicles to service the transportation needs of its customers. Each customer enters their pickup point (node number in graph) and drop-off point (also a node number) when placing a request. The system responds by assigning a vehicle to the customer and letting the customer know an estimate of the pickup time in minutes. This estimate may be an underestimate of the actual waiting time if the assigned vehicle picks up another passenger on its way to the original passenger but for the purposes of this project, we will let the estimate stand – i.e., the estimated passenger waiting time will not be updated. All vehicles are identified by an integer in the range 1 to N. Vehicle assignment to a customer must account for proximity of the vehicle to the customer’s pickup location – the vehicle closest to it will be assigned the customer. This means that the agent needs to keep track of the current location of all vehicles in its fleet. For the purposes of this project, we will assume that vehicles travel at a constant speed of 30mph.
As the company provides a ride sharing service to keep its cost to the customer down, it may assign as many customers as there are seats available. The passenger capacity is 5. Customer pickups may not be serviced in the order that they were issued. In case more than one customer/customer group is present in the vehicle the agent needs to work out the order in which the customers will be dropped off. You should not assume that the drop offs will be in first come first served order. This means that the agent will need to work out the optimal drop off order in terms of the minimum distance to be traversed to serve the needs of the customers in the vehicle, taken collectively. Thus, for example, if there are 2 passengers A and B in the vehicle, with A having hired the vehicle before B, then it is possible that B will be dropped off before A if after taking on B it so happens that B’s destination is on the way to A’s destination. This means that route planning must be dynamic, once a new passenger is taken on the route must be updated to account for the new passenger’s destination.
We will also assume that cancellations are not made by either the customer or the company once a reservation has been made.
If a vehicle is not assigned a new passenger after dropping off its last one, then it simply parks at the drop off point and waits for the next passenger to arrive. We will assume that parking is always available.
Your task in this project is to implement the following requirements:
Q1. Produce a pseudo code version of the algorithm needed to assign a vehicle to a customer.
Q2. Produce a pseudo code version of the algorithm needed to plan a route for dropping off passengers in a given vehicle.
Q3 Implement a Python program that incorporates the two algorithms in Q1 and Q2 above.
Q4. Assume that the rideshare is provided in an 8-hour timespan in which bookings are accepted; that the company operates a fleet of 30 vehicles and that an average number of 200 reservations per hour, what is the average distance travelled per day taken across the entire fleet and over the entire day?
Note that reservations occur at random points in the clock and may originate at random nodes in the graph. Likewise, destinations are also random but must not be less than 20 nodes from the pickup node.
Q5. Now vary the fleet size to 60 vehicles and suppose that an average of 400 reservations occur per hour with the same constraints mentioned in Q5 above. What is the new value of the average distance travelled per day taken across the entire fleet and over the entire day?
Q6 Now run your code across the new graph shown below. What is the new value of the average distance when the conditions given in Q4 are applied? Why does it differ?
Hand in:
1) A short report (between 1 and 2 pages in size) describing the approach that you took. In addition to the description of your approach you should answer the 6 questions given above. Note: one team member should undertake the design and coding of the customer pickup while the other concentrates on the drop off functionality. A clear demarcation of contribution is required.
2) Any assumptions that you made while undertaking this project.
3) The complete set of Python code that you used. This needs to be submitted both as a pdf document (no images please) as well as your original Jupyter/Google Colab notebook.