Project 2: Multi-Player Games (due Sep-17 at 11:59pm)
Table of Contents
Coordinate robots.
Minimize travel time.
Introduction
In this task you will be helping delivery robots to plan paths within a logistic warehouse. You will observe the impact of an accurate heuristic function on the computational efficiency.
The code for this project contains the following files, available as a zip archive.
| Files you'll edit: | |
SingleAgentState.py |
Defines the logic for a state when used to solve a single agent pathfinding problem with best-first search. |
MultiagentState.py |
Defines the logic for a state when used to solve a multiagent pathfinding problem with best-first search. |
CBS_State.py |
Defines the logic for a state when used to solve a multiagent pathfinding problem with conflict-based search. |
| Files you might want to look at: | |
Robot.py |
The definition of the robot agent. This class defines the robot's actions, plan, and goal. |
BestFirstSearch.py |
A best-first search implementation. This class can run on any problem that defines the state space adequately. |
main.py |
The main file that runs the warehouse simulator. |
Files to Edit and Submit: You will fill in
portions of SingleAgentState.py,
MultiagentState.py, and CBS_State.py
during the assignment. You should submit these file with your code
and comments. Please do not change the other files in this
distribution or submit any of our original files other than these files.
You may add new files (needed for the CBS implementation).
Evaluation: Your code will be autograded for technical correctness. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. However, the correctness of your implementation -- not the autograder's judgements -- will be the final judge of your score. If necessary, we will review and grade assignments individually to ensure that you receive due credit for your work.
Academic Dishonesty: We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else's code and submit it with minor changes, we will know. These cheat detectors are quite hard to fool, so please don't try. We trust you all to submit your own work only; please don't let us down. If you do, we will pursue the strongest consequences available to us.
Getting Help: You are not alone! If you find yourself stuck on something, contact the course staff for help. Office hours, section, and the discussion forum are there for your support; please use them. If you can't make our office hours, let us know and we will schedule more. We want these projects to be rewarding and instructional, not frustrating and demoralizing. But, we don't know when or how to help unless you ask.
Discussion: Please be careful not to post spoilers.
The Warehouse Environment
The warehouse layout is given as a 4-connected grid. One or more robots operate inside the warehouse. Each robot has 10 different actions that it can perform. Only one action can be performed per time step. Each of the available action takes exactly one time step to perform. Some actions might be inadmissible at some states. The set of available actions are:
-
turn_north= change the robot’s heading to face North -
turn_east= change the robot’s heading to face East -
turn_south= change the robot’s heading to face South -
turn_west= change the robot’s heading to face West -
accelerate= increase the speed of the robot by 1 (cell/time step). The speed limit is currently set to 1. -
decelerate= reduce the speed of the robot by 1 (cell/time step). The speed cannot be lower than 0. -
lift= pick up a package. Only applicable if the robot is in the same location as the package and has a velocity of 0. -
drop= drop a package. Only applicable if the robot is carrying a package and has a velocity of 0. -
no_op= do nothing (the robot will still advance if its velocity is not 0). -
process= process a mounted package at a processing station.
Getting Started
Run:
python main.pyNotice a single robot is delivering random pods to random packing stations. For each of the robot’s tasks (go to pod, go to station, put pod back) the robot computes and executes the shortest path by running uniform cost search. You can notice that each planning episode stops the program for a fraction of a second (watch the time step counter on the upper right corner). Open
main.py, change the scenario from Warehouse-1.map to arena2-1.map.
This is a much bigger map and UCS is very slow to plan.
Question 1: Single Agent Heuristic
Your first task is to utilize the A* algorithm by setting an
admissible heuristic value in the single-agent state. You should be
able to run arena2-1.map reasonably fast (<5 second
per planning phase)
Open Planning/SingleAgentState.py, add an admissible
heuristic for the single-agent case (see # TODO: Your job -
Set a better heuristic value.).
Tip: you can use self.robot.position_x for the
robot’s x coordinate and self.robot.goal_x for
the goal’s x coordinate. Same goes for the y coordinates.
Grading:
- Score 0 for non-admissible heuristic OR expanding more than 31,820 and 87,610 states on the first and second iterations of
arena2-1.maprespectively - Score +1 for admissible heuristic that expands less than 31,820 and 87,610 states on the first and second iterations of
arena2-1.maprespectively - Score +1 for admissible heuristic that expands less than 30,230 and 85,460 states on the first and second iterations of
arena2-1.maprespectively - Score +1 for admissible heuristic that expands less than 30,000 and 85,000 states on the first and second iterations of
arena2-1.maprespectively
Question 2: Multiagent Heuristic
Open main.py, change the scenario field from arena2-1.map to
Toy-MAPF-2.map. This is a multiagent pathfinding problem with 2
agents. This instance is solved with UCS on the combined
state-space. UCS can easily overcome this simple problem. Now,
change Toy-MAPF-2.map to Warehouse-MAPF-2.map UCS for
multiagent planning is now very slow to run.
Your second task is to utilize the A* algorithm by setting an
admissible heuristic value in the multiagent state. You should be
able to run Warehouse-MAPF-2.map reasonably fast (<5 second per
planning phase)
Open Planning/MultiagentState.py, add an admissible
heuristic for the multiagent case (see # TODO: Your job -
Set a better heuristic value.).
Grading:
- Score 0 for non-admissible heuristic OR expanding more than 13,000, 8,700, and 1,100 states on the first, second and third iterations of
Warehouse-MAPF-2.maprespectively - Score +1 for admissible heuristic that expands less than 13,000, 8,700, and 1,100 states on the first, second and third iterations of
Warehouse-MAPF-2.maprespectively - Score +1 for admissible heuristic that expands less than 7,130, 3,350, and 300 states on the first, second and third iterations of
Warehouse-MAPF-2.maprespectively - Score +1 for admissible heuristic that expands less than 7,100, 3,300, and 290 states on the first, second and third iterations of
Warehouse-MAPF-2.maprespectively
Question 3: Conflict-Based Search
Open main.py, change the scenario field from Warehouse-MAPF-2.map to
Warehouse-MAPF-3.map. This is a multiagent pathfinding
problem with 3 agents. Multiagent A* is very slow to run on 3 agents.
Your third task is to implement the CBS algorithm. This is an optional, bonus task (it is not trivial to implement).
Open Planning/CBS_State.py, implement all required
functions (you will need to add several more functions/classes). Open
main.py, change RobotNoCarry.ma_planner to equal CBS
instead of maA*. Try to run on the same scenario but with more
agents lak303d-MAPF-k.map. for k={2,3,4,5,10}.
Grading:
- Score +20 (bonus) for correctly implementing CBS.