Project informations
Description of the projectThis is project is the realisation of an assignment for :<h2>Master IA of the universitat politècnica de catalunya (Barcelona, España) assignatura de IA Laboratory Assignment 1 September 22nd 2008 </h2> Satement of the assignment: "The goal of this assignment is to use the java classes explained in the laboratory sessions to solve the following local search problem. The Barcelona city council has decided to start a service of car pooling to help reduce city trac and CO2 emissions. Each user in this service says how many available seats has in his car, his home address and his work address. Each month it is the turn of a dierent group of users to provide the vehicles for car pooling (we will suppose that all users have always three seats available). During that month people that are sharing their car adapt their route to pick up other users and take them to work. During the route the car could pick up more people than available seats if the routes of this people are disjoint. We have a constraint about the routes that is that the driver of the car has to arrive to his work on time, that limits the total length of the route. We will suppose that the mean speed of city trac is 30 km/h, the car starts its route at 7 AM and the driver has to arrive at work before 8 AM. To simplify the problem we will suppose that the city is a square of 1010 kilometers and the streets are a grid where each block is 100100 meters. The addresses of the users and their destinations correspond to intersections of the grid. The distance between two points inside the city will be calculated as: d(i; j) = jix jxj + jiy jyj Where ix and iy are the coordinates x and y of the i point of the grid. We need to obtain the solution for this problem for a given month, we want a plan that for each person that shares his car that month has a route that allows to pick up and take to their work a set of users respecting the number of available seats in the car and the other constraints. Keep in mind that a solution has to take everybody to their work. The main goal is to minimize the total length of the routes of the cars. Implement the classes needed to solve the problem using the AIMA classes seen in the labora tory sessions. Produce a report of the work which includes the source code of these classes. The implementation has to be able to generate dierent randomly generated problems that allow the change the following parameters: The number of users that share their car and the number of users to be picked up. The spatial distribution of the home address of the drivers (uniform, clustered in one part of the city, clustered in some parts of the city). The rest of addresses should be random. Experiment with dierent strategies (two at least) to generate the initial state. The problem may have to start from a state that is not a solution. Choose and test dierent sets of search operators. Experiment with two heuristic functions: A function that minimizes the total length of the routes A function that minimizes the total length of the routes but prioritizes that all routes are approximately the same length If the search initiates from a state that is not a solution you will have to think about what is necessary to add to the heusitic functions to guide the search to the solutions space Design a set of experiments for each algorithm (Hill Climbing and Simulated Annealing) to answer the following questions: Given a total number of users What proportion between drivers and users to be picked up gives the better solutions? Is this proportion the same if the number of users is changed? Think that there will be proportions that will not give any solution. Does the distribution of the cars inside the city have any inuence in the quality of the solutions? Is there a signicative dierence among the solutions obtained using the two heuristic functions? In order to answer this questions you have rst to nd out what strategy of initialization is better and the most suitable set of search operators. To do this you have to choose a specic scenario and perform some experiments. You have to decide what values to use for the dierent parameters of the problem in the experiments and to give a justication of your decisions. In the case of the Simulated Annealing algorithm, explore also the eect of dierent values for its parameters Explain and justify all the decisions that you make. The conclusions must include: Comments about the results of each experiment. Explain what you expected and what hap pened. Comparison of the two local search algorithms using the results of the experiments (quality of the solutions and execution time). It is essential to be systematic in the experimentation process, do not make your decisions ran domly. Use the results of each experiment to guide your decisions. Statistics and graphics could be a good way to support your conclusions. The grade will depend on the quality of the experiments performed, the quality of the comments and conclusions and the quality of the written report. This assignment has to be solved preferably by teams of two students. The report and the code are due by November 3rd by 5 PM. The deliver will be by email to luigi@lsi.upc.edu. It is important to plan the development of this assignment and do not do all the work at the last moment." 
Technical specifications
Language(s):
Available translation(s):
Targeted system(s):
Tags
Get involved
Project administrators
