In this first exercise you are asked to implement an environment simulator that runs a path optimization problem. Then, you will implement some agents that live in the environment and evaluate their performance.
We are given a weighted graph, and the goal is (starting at a given vertex) to visit as many as possible out of a set of vertices, and reach a given goal vertex before a given deadline. However, unlike standard shortest path problems in graphs, which have easy known efficient solution methods (e.g. the Dijkstra algorithm), here the problem is that there are more than 2 vertices to visit, their order is not given, and even the number of visited vertices is not known in advance. This is a problem encountered in many real-world settings, such as when you are trying to evacuate people who are stuck at home with no transportation before the hurricane arrives.
The environment consists of a weighted unidrected graph. Each vertex may contain a number of people to be evacuated, or a hurricane shelter. An agent (evacuation vehicle) at a vertex automatically picks up all the people at this vertex just before starting the next move, unless the vertex contains a hurricane shelter, in which case everybody in the vehicle is dropped off at the shelter (goal). It is also possible for edges (roads) to be blocked, in this assignment we assume complete knowledge so w.l.o.g. all edges are initially unblocked.
An agent can only do no-op (taking 1 time unit) or traverse actions. The time for traverse actions is equal to: w(1+Kp), where w is the edge weight, p is the number of people in the vehicle, and K is a known global non-negative "slow-down" constant, determining how much the vehicle is slowed due to load. The action always succeeds, unless the time limit is breached.
The simulator should keep track of time, the number of actions done by each agent, and the total number of people successfully evacuated.
Initially you will implement the environment simulator, and several simple (non-AI) agents. The environment simulator should start up by reading the graph from a file, as well as the contents of vertices and global constants, in a format of your choice. We suggest using a simple adjancency list in an ASCII file, that initially specifies the number of vertices. For example (comments beginning with a semicolon):
#V 4 ; number of vertices n in graph (from 1 to n) #E 1 2 W1 ; Edge from vertex 1 to vertex 2, weight 1 #E 3 4 W1 ; Edge from vertex 3 to vertex 4, weight 1 #E 2 3 W1 ; Edge from vertex 2 to vertex 3, weight 1 #E 1 3 W4 ; Edge from vertex 1 to vertex 3, weight 4 #E 2 4 W5 ; Edge from vertex 2 to vertex 4, weight 5 #V 2 P 1 ; Vertex 2 initially contains 1 person to be rescued #V 1 S ; Vertex 1 contains a hurricane shelter (a "goal vertex" - there may be more than one) #V 4 P 2 ; Vertex 4 initially contains 2 persons to be rescued #D 10 ; Deadline is at time 10
The simulator should query the user about the number of agents and what agent program to use for each of them, from a list defined below. Global constants and initialization parameters for each agent (initial position) are also to be queried from the user.
After the above initialization, the simulator should run each agent in turn, performing the actions retured by the agents, and update the world accordingly. Additionally, the simulator should be capable of displaying the state of the world after each step, with the appropriate state of the agents and their score. A simple screen display in ASCII is sufficient (no bonuses for fancy graphics - this is not the point in this course!).
Each agent program (a function) works as follows. The agent is called by the simulator, together with a set of observations. The agent returns a move to be carried out in the current world state. The agent is allowed to keep an internal state (for example, a computed optimal path, or anything else desired) if needed. In this assignment, the agents can observe the entire state of the world.
You should implement the following agents:
At this stage, you should run the environment with three agents participating in each run: one greedy agent, one vandal agent, and one other agent that can be chosen by the user. Your program should display and record the scores. In particular, you should run the greedy agent with various initial configurations. Also, test your environment with several agents in the same run, to see that it works correctly. You would be advised to do a good job here w.r.t. program extensibility, modularity, etc. much of this code may be used for some of the following assignments as well.
Now, after chapter 4, you will be implementing intelligent agents (this is part 2 of the assignment) that need to act in this environment. Each agent should assume that it is acting alone, regardless of whether it is true. You will be implementing a "search" agent as defined below. All the algorithms will use a heuristic evaluation function of your choice.
The performance measure will be composed of two parts: S, the agent's score, and N, the number of search expansion steps performed by the search algorithm. The performance of an agent will be:
P = f * S + N
Clearly, a better agent will have P as small as possible. The parameter f is a weight constant. You should compare the performance of the three agents (each acting alone) for the following values of f: -1, -100, -10000. Note that the higher (in absolute value) the f parameter, the more important it is to expend computational resources in order to get a better score!
Bonus version: construct a search agent as above, but in addition allow one vandal agent also acting in the environment. Your search agent needs to take this into account. Observe that although this seems to be a multi-agent problem, the fact that vandal is perfectly predictable makes this in essence a single agent search problem.
Addtional bonus - theoretical: What is the computational complexity of the Hurricane Evacuation Problem (single agent)? Can you prove that it is NP-hard? Or is it in P? If the latter, can you design an algorithm that solves the problem in polynomial time?
The program and code sent to the grader, by e-mail or otherwise as specified by the grader, a printout of the code and results. A document stating the heuristic function you used and the rationale for selecting this function. Set up a time for frontal grading checking of the delivered assignment, in which both members of each team must demonstrate at least some familiarity with their program...
Due date for part 1 (recommended, not enforced): Wednesday, October 31.
For the complete assignment: Tuesday, November 13.