Final Project Assignment
ROUTE SEARCH IN LOGISTICS PROBLEMS
Artificial Intelligence Computer Science Degree Spring 2019
In this project you will work with search algorithms to be applied in a simulated environment where a delivery person has to deliver pizzas to different predefined locations. The problem environment is discretized as shown in Figure 1. The delivery person starts his route from his base, where he has to return once all the pizzas are delivered. Tiles depicted as green buildings are those where the delivery person has to deliver the pizza. Tiles depicted as a pizza are restaurants where the delivery person can stock up on pizzas. The environment may have different types of terrains.
The programming language is Python. For purposes of this work, we will use the library SIMPLE-AI 0.8.1 (https://pypi.python.org/pypi/simpleai/), which implements many artificial intelligence al- gorithms, including uniformed and informed search algorithms.
The project consists of two parts:
• Part I (7p): a basic part that consists of solving a problem in different environments using different search algorithms.
• Part II (3p): an advanced part that consists of including additional characteristics to the simplified prob- lems, such as types of terrain, number of orders per client, maximum load capacity, etc.
1 Basic problem (7p)
The idea is to solve a search problem where a delivery person rides his bike from his base to different locations to deliver pizzas; then he rides back to his base. For purposes of this part, you must take into consideration that (1) there is only one restaurant, (2) there is only one client, who can make two orders at most; (3) the maximum load capacity of the delivery person’s bike is two; (4) the delivery person cannot ride through tiles different than delivery locations or restaurants; and (5) all actions have unit-cost. The total cost of the solution is the total number of actions performed by the delivery person (movements between tiles, loading pizza, and unloading pizza).
Student’s task
Your task consists of two parts:
1. Design and implementation: you will design and implement the problem representation (state and ac- tions), a non-trivial heuristic function, and other additional functions required by the search module SIMPLE-AI. Additionally, you must run different search algorithms to solve the problem in order to check that the implementation is correct.
2. Experimental evaluation and comparison:
1
Figure 1: Problem example: the delivery person is located at his base; green buildings represent delivery loca- tions and the number of orders in each building; the pizzas represent restaurant locations; gray tiles represent roads; other buildings represent apartment complexes that the delivery person cannot cross.
• An experimental evaluation to solve the basic problem by using different search algorithms. The SIMPLE-AI library includes, among others, the following search algorithms: breadth first, depth first, limited depth first, astar (an example of a call to any of these algorithms is included in the given code). You will do a comparison among the different search algorithms considering number of expanded nodes, cost of the solution, and memory usage. Information about the solution is shown at the end of the simulation.
• Development of at least three new scenarios that you consider interesting. Then, you will repeat the previous process to compare them. You can: evaluate the same scenario with and without terrain types representing obstacles, modify the size of the grid, number of goals and their locations, etc. You must analyze the impact of these changes in the solution of the problem.
Software installation
To develop this project, you need to install Python 2.7 and the packages pygame and pydot1. To install the software, unzip 201819 AI software.zip. To execute it, open a command line terminal and type python startGame.py.
The files that you must modify are in the student folder, which has the following files: • config.py, which defines the initial settings for the problem.
• gameProblem.py, which contains the functions required by the search module SIMPLE-AI and that must be implemented.
• map.txt, which defines the configuration of the problem. Code description
You will implement some functions required by the search module SIMPLE-AI. You will do that in the gameProblem.py file given, which contains a class with the same name and the definition of the functions that need to be implemented (indicated with comments in the code).
The class gameProblem represents the search problem. It has a list of attributes (described in the Appendix) that you can use to access the grid, types of terrains, etc. These variables can be consulted, but cannot be modified.
1These are already installed in the machines at the university.
2
The functions you need to implement are the following:
2
• actions(s): function that receives a state s and returns a list of applicable actions in s.
• result(s1,a): function that receives a state s1 and an action a and returns a state s2, which is the result of applying a in s1.
• is goal(s): functions that receives a state s and returns True if s is a goal state. Otherwise, it returns False.
• cost(s1,a,s2): function that receives two states s1 and s2 and an action a, and returns the cost of achieving
s2 from s1 applying a.
• heuristic(s): function that receives a state s and returns the heuristic value of s; that is, the estimated cost
of reaching the goal state from s.
• setup(): function that configures the initial state, the goal state, and the search algorithm to use.
• printState (s): function that receives a state s and prints its value in the interface.
• getPendingRequests (s): functions that receives a state s and returns the number of pending orders, if s is a delivery location. Otherwise, it returns None.
Advanced problem (3p)
The idea is to perform a similar experimental evaluation as before, but using problems with additional charac- teristics. To include them, you will need to make some changes in the design and implementation developed in Part I. We propose to include the following:
• Terrain with costs. Each terrain type will have a different cost of riding through it. This cost could represent, for instance, the time consumed (it is easier to ride on a flat road that on a hill). These costs could be modified in the configuration file.
• Cost per load. Consider that the cost of the actions depends on the actual load.
• Heuristics. Define different heuristics and evaluate them.
3 Submission
This project should be done in pairs. You must submit a zip file through a link that will be posted on Aula Global. Note that, if you work in pairs, only one submission is needed. The zip file name must be pr-ai-2019- students-code.zip, where students-code is the last six digits of each students’s NIA (e.g., pr-ai-2019-123456- 654321.zip). The zip file will consist of:
• An essay containing the following sections (PDF file):
1. Introduction 2. For each part:
– Description and explanation of the tasks performed within the project: problem representation and implemented functions.
– Description and explanation of the performed tests and the results obtained from such tests. 3. Conclusions: technical comments related to the development of this project.
4. Personal comments: difficulties, challenges, benefits, etc.
• A directory, namely pr-ia-2019/student-code, containing the source code, including the parts you have implemented and the other folders needed to run the project.
The deadline for the submission of the project is on May 12th at 11.55pm! 3
Appendix: software documentation
The given software consists of the following elements:
1. The SIMPLE-AI library, which implements the search algorithms.
2. The GAME-IA library, which is the graphic component. It consists of several files that must not be modified.
3. The GAMEPROBLEM class, which is the class where you have to do your implementation.
Toexecutethegameopenaterminalandtypepython startGame.py
The graphical component interacts with the student’s component in the following way:
1. During the initialization of the game, and object of gameProblem is created.
2. Then,thefunctionsetup()isinvoked;hereyoumustspecifytheinitialstate,thegoalstate,andthesearch
algorithm.
3. The search is performed using the search algorithm specified and returns a solution, if there is one. Then, the output shows the statistics for the performed search process.
4. The graphical component performs a simulation to show the solution found. To do that, it simulates the solution using the predefined actions: ’North’,’East’,’South’,’West’ (the graphical component ignores any other action).
The output shows information about the performed search; it could be useful for the experimental part.
total length of solution: 47
total cost of solution: 51
visited nodes: 8001
iterations: 8001
max fringe size: 554
You could save this output in a file.
Configuration file
The configuration file config.py defines the configuration parameters of the problem. They are described in Table 1. You can modify the values of the fields of this file. Table 2 describes the fields of a tile. The basic tile is defined in basicTile. You can access the attributes by calling the method GETATTRIBUTE(POSITION, KEY).
Each tile has two different versions that have identical attributes. One of them has the prefix -traversed; it is used by the simulator to change the color of the tile when the delivery person rides through it. Tiles tagged as traversed are not considered during the search process.
The gameProblem class
Table 3 describes the attributes of the gameProblem class, which has the definition of the finctions that you must implement.
4
Table 1: Description of fields of the configuration file Description
Font size
Cell size
Generates a random grid
Loads a grid from a file
Seed for the random number generator File to load or save a grid
True, save the grid to a file
Grid size (column, row)
Simulation speed (0.1)
True, shows the MAP variable
default tile
Maximum load capacity
Information about the agent
Initial position of the agent (column, row) Cells configuration
Do not modify
Do not modify
Table 2: Description of fields in tile
Type
Int
Int “random” “load”
Int String Boolean Tuple (Int, Int) Float Boolean String (key) Int
Dict. Tuple (Int, Int) Dict.
Attribute “text size” “tile size” “type”
“seed”
“file”
“save”
“map size” “delay” “debugMap” “basicTile” “maxBags” “agent” “agent[’start’]” “maptiles” “debug” “hazards”
Attribute Description
Type
String String Char Int Dict.
Dict.
graphics id marker num state
attributes
File containing the graphical image for the tile
Id of the tile in MAP and POSITIONS.
Character used to symbolize the tile when loading or reading a grid from a file Number of tiles of this types in the grid when randomly generated
Number of tiles of this type in the grid
“agent” initialized to None
Dictionary with attributes such as:
“cost” indicates de cost of the tile
“objects” indicates the number of orders
Table 3: Description of attributes in gameProblem Attribute Description
Type
List [0] [1] [2]
Dict. key value
Dict.
Tuple [0] [1]
Student definition
Student definition
Student definition
Int
MAP
POSITIONS
CONFIG AGENT START
Map of the grid. Each tile is a list of:
Type of tile
Id
Attributes of the tile, loaded from the configuration file It contains the keys to all types of tiles of the grid Type of tile
List of the positions for the tiles of the type in key Configuration from configuration file
Initial position of the agent (from configuration file) Coordinate X
Coordinate Y
INITIAL STATE Initial state, loaded during the initialization phase
SHOPS CUSTOMERS MAXBAGS
Restaurant positions, loaded during the initialization phase Clients positions, loaded during the initialization phase Maximum load capacity, loaded during the initialization
5