| marp | true |
|---|---|
| _class | invert |
| paginate | true |
| backgroundColor | |
| color | |
| theme | default |
| transition | fade 0.3s |
| footer | Optimisation and Planning Summer School 2025 |
In this tutorial, you'll learn to develop a multi-agent path planning algorithm that can navigate through a shared environment in League of Robot Runners.
Find these slides at: https://pathfinding.ai/opss25-tutorial/
Before we get going we'll need to:
- Go through a bit of background
- 📦 Use our script to set up your development environment
- 📝 Clone our starting repository
- 👀 Get familiar with the software we'll be using
https://www.leagueofrobotrunners.org/
We're going to build a system that can plan like this ->
Lets see if that gets you motivated. Details for how to join at the end of the session.
Open up a terminal and run the following command:
curl -fsSL https://pathfinding.ai/opss25-setup/install | bashwget -qO- https://pathfinding.ai/opss25-setup/install | bashpowershell -c "irm https://pathfinding.ai/opss25-setup/install.ps1 | iex"Navigate to a chosen directory in Terminal. Run the following command (using your preferred of https or SSH):
git clone https://github.com/ShortestPathLab/opss25-startkit.git
git clone git@github.com:ShortestPathLab/opss25-startkit.gitSupport: for those unfamiliar with Git, we recommened visiting the Github Docs for cloning a repository.
Navigate to the newly created directory and explore by running:
cd opss25-startkit
lsWe recommend opening the Start Kit in your favourite IDE. The codebase you'll be working on are in the a1-a4 branches. We'll tell you when to switch branches.
Navigate to the OPSS25 top directory. Switch to a bash shell by running bash.
Activate your new OPSS25 environment by running:
conda activate opss25To test the setup, run the following command:
opss25-lifelong --inputFile example_problems/random/random_1.json -s 100If this executes successfully, you are good to go!
Please raise your hand and we will come over to help.
- Problem: conda not recognised, Solution:
conda init bash. If this doesn't work, thensource activate base
This is a modified version of the Startkit that the League of Robot Runners participants used. It gives you the command opss25-lifelong to run the planner.
This is the search library that we'll use to do path planning.
Multi-agent visualiser for the League of Robot Runners.
Visualise search procedures in depth.
You must first generate planviz files by running the planner:
opss25-lifelong --inputFile example_problems/random/random_1.json --output output.json -s 100You can run the Planviz visualiser using the following command:
opss25-planviz --plan <json_file> --map <map_name>You can find the map files in the example_problems directory.
You can get the planner to generate a Posthoc file by setting LOG_ENABLED=True in pyMAPFPlanner.py to true.
Then you may drag the created .trace.yaml file into Posthoc.
Use this development version of Posthoc: https://spaaaacccee.github.io/posthoc-next/
In this exercise, we are going to implement the basic Lego blocks of search:
This is the expander that generates valid successors of the current state.
This is a function that estimates the cost of reaching the goal from the current state.
Switch to the A1 branch to continue: git checkout a1
During search, an expander generates valid successors of the current state. This means that expanders are domain-dependent, and must be modified to match the `rules' of the world.
In this exercise, your task is to implement an expander for the RobotRunners competition. Robots are able to perform the following actions:
- Move forward one step,
- Rotate 90 degrees either clockwise (CW) or counter-clockwise (CCW),
In ex1_lorr_expander.py, read through expand() and modify the helper functions get_actions() and move() to generate nodes based on the above actions each robot can perform.
HINT: in get_actions(), you need to make sure that moves are valid within the environment.
We now have a way to generate new states, but we also have to evaluate which looks the most promising!
Nodes in A* are ranked by
Unlike what we have seen of heuristics in PDDL, in pathfinding we aim to implement domain-dependent hueristics. Let's have a quick look at implementing a couple.
Your task is to implement the:
manhattan_distance_heuristic(),octile_distance_heuristic(), andstraight_line_distance()
Manhattan distance returns the optimisitic grid-distance between any two locations (ignoring obstacles).
The Octile distance returns a similar estimate, but it allows diagonal movements (cost =
Time to put your search together!
In a1/ex3_create_search.py, you'll find the scaffolding for a search engine. Modify it to use the manhattan distance heuristic and the expander you implemented in the previous exercise:
Run the start kit with one agent:
opss25-lifelong --inputFile example_problems/random/random_1.json -s 100Then, visualise your solution:
opss25-planviz --plan=output.json --map=example_problems/random/maps/random-32-32-20.mapIf on Apple Silicon, you may need to run source activate base from your bash shell.
Not all heuristics are equal. What do we want from a heuristic?
Task: Modify the manhattan distance heuristic to be direction-aware.
We have provided a template for get_init_turns to help calculate the number of turns that may be required for an agent to face in one of the heuristic-recommended directions.
Hint: agents may require some number of turns to face the correct direction, and then may need to bend their path.
You should now have a working A* search.
-
💡 Check out the
ex4_basic_planner.pyfile. It contains the structural code that runs your search engine in the context of the robot runner start kit. -
💡 Experiment with various heuristics.
-
💡 Try creating a visualisation using Posthoc.
We now have a working low-level search! Agents can get where they need to go.
But agents are not alone. Agents must plan paths in a shared environment.
Switch to the a2 branch to continue. We have already filled out the expander from a1 for you.
Let's see what happens when we plan paths for two agents. Run and observe the output:
opss25-lifelong --inputFile example_problems/random/random_2.json -s 500
opss25-planviz --plan=output.json --map=example_problems/random/maps/random-32-32-20.mapEvidently, we have an issue now. Agents must learn to avoid each other!
In this Exercise, we will work on implementing a way of tracking locations that agents occupy in order to avoid collisions. We call this data strcture a reservation table, and it has two main methods:
reserve(state)(reserves a specific location for an agent),is_reserved(state)(which checks if a location is reserved)
In your code, you will see template functions for these two functions. It is your task to complete the implementation. You are safe to assume that the class has an inbuilt vertex_table, which is a 2D array indexed by [x][y].
You will also need to complete this implementation---agents need to reserve their location in our high-level planner! To do so, you will need to:
- modify your
expanderso that it does not generate new states if there is a collision! - modify the
high-level plannerto make agents reserve their path. We can call the low level planner every single time step to make things easier.
Test your implementation (what looks different?):
opss25-lifelong --inputFile example_problems/random/random_2.json -s 100
opss25-planviz --plan=output.json --map=example_problems/random/maps/random-32-32-20.mapdef reserve(self, *states: list[robotrunners_state]):
for state in states:
x, y, *_ = state
self.vertex_table[x][y] = Truedef is_reserved(self, state: robotrunners_state):
x, y, *_ = state
return self.vertex_table[x][y]def expand(self, current):
self.succ_.clear()
for a in self.get_actions(current.state_):
new_state = self.move(current.state_, a.move_)
if self.reservation_table_.is_reserved(new_state):
continue
self.succ_.append((new_state, a))
return self.succ_[:]def plan(
env: MAPF.SharedEnvironment,
paths: list[list],
last_did_error: bool = False,
):
table.clear()
for i in range(len(paths)):
paths[i] = run_search(env, i)
# Check if we've got a solution
if paths[i]:
# Reserve all points on the path
table.reserve(interop.get_agent_state(env, i), *paths[i])
return pathsWhile our agents now reserve their paths, this is done naively. You see a lot of agents fail to find a solution, and thus not move (no agents actually occupy these locations!).
In the simulator, agents plan paths at each timestep anyways.
- 💡 As such, we can avoid collisions by only checking next-step reservations.
Task: modify the expand() function to check for collisions only for the first step in your path.
Test and visualise your implementation - do things seem to improve?
def plan(
env: MAPF.SharedEnvironment,
paths: list[list],
last_did_error: bool = False,
):
table.clear()
for i in range(len(paths)):
paths[i] = run_search(env, i)
# Check if we've got a solution
if paths[i]:
# Reserve only the first point on the path
table.reserve(interop.get_agent_state(env, i), paths[i][0])
return pathsYou can now plan collision-free paths for multiple agents in a shared environment.
-
💡 Experiment with visualising various scenarios.
-
💡 Think about how we can improve our existing systems
After the break, we will expand upon these ideas to bridge the gap to MAPF algorithms and lifelong planning.
Go to the contest server https://opss25.contest.pathfinding.ai/
Click Sign in with GitHub.
Authorise the app to access your profile.
We're going to create a submission repository.
Click Create repository.
Your repository should be created for you.
Click open repository.
You'll may get asked to accept an invitation to the repository.
Click Accept invitation.
Now you're free to push your code to this repository 🎉
You'll may get asked to accept an invitation to the repository.
Click Accept invitation.
Now you're free to push your code to this repository 🎉
When you push to that repository, it'll be available to be selected. Click Submit, and verify that it's queued up below.
Click on a submission to check out its details.