# Pathfinding
Pathfinding is the problem of finding the best route between two points.
<p align="left">
<img src="https://raw.githubusercontent.com/w9PcJLyb/pathfinding/refs/heads/main/images/pf_grid.png" width="128"/>
</p>
This repository includes several pathfinding algorithms:
| Algorithm | Class name | Optimal |
| ----------- | ----------- |----------- |
| Depth-first search | DFS | False |
| Best-first search | GBS | False |
| Breadth-first search | BFS | True (only in an unweighted graph) |
| Bidirectional Breadth-first search | BiBFS | True (only in an unweighted graph) |
| Dijkstra | Dijkstra | True |
| Bidirectional Dijkstra | BiDijkstra | True |
| A* | AStar | True |
| Bidirectional A* | BiAStar | True |
| Iterative deepening A* | IDAStar | True |
Example:
```python
from w9_pathfinding import Graph, Dijkstra
graph = Graph(num_vertices=4)
graph.add_edges(
[
(0, 1, 1), # start, end, cost
(0, 2, 3),
(0, 3, 4),
(1, 3, 1),
(2, 3, 1),
]
)
dijkstra = Dijkstra(graph)
path = dijkstra.find_path(start=0, goal=3)
print(path) # [0, 1, 3]
```
# Multi-Agent Path Finding (MAPF)
Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for a group of agents from their location to an assigned target.
<p align="left">
<img src="https://raw.githubusercontent.com/w9PcJLyb/pathfinding/refs/heads/main/images/mapf_hex.gif"/>
</p>
Implemented algorithms:
| Algorithm | Class name | Optimal | Complete |
| ----------- | ----------- |----------- | ----------- |
| Hierarchical Cooperative A* | HCAStar | False | False |
| Windowed Hierarchical Cooperative A* | WHCAStar | False | False |
| Conflict Based Search | CBS | True | True |
| Increasing Cost Tree Search | ICTS | True (only in an unweighted graph) | True |
| A* with Operator Decomposition | MultiAgentAStar | True | True |
Here optimality means that the algorithm can find the optimal solution in terms of Sum-of-costs function.
Example:
```python
from w9_pathfinding import Grid, WHCAStar
grid = Grid(
# -1 - unwalkable cell
# >= 0 - walkable, value is the cost of moving to this cell
weights =[
[1, 1, 1, -1],
[-1, 1, 1, -1],
[1, 1, -1, -1],
[1, 1, 1, 1],
],
edge_collision=True, # head to head collisions are not allowed
)
whcastar = WHCAStar(grid)
paths = whcastar.mapf(starts=[(0, 0), (1, 1)], goals=[(2, 0), (1, 0)])
print(paths) # [[(0, 0), (1, 0), (2, 0)], [(1, 1), (1, 1), (1, 0)]]
```
# Pathfinding with dynamic obstacles
To manage dynamic obstacles in pathfinding, a ReservationTable can be used. This data structure tracks the availability of each cell or edge over time, indicating whether it is free or reserved. In the case of the single-agent pathfinding problem with dynamic obstacles, there is a specialized version of the A* algorithm known as Space-Time A* (SpaceTimeAStar).
Let's look at a simple example. We have three agents: Agent 0, Agent 1, and Agent 2. Agent 0 has a predetermined path that we cannot change, this agent acts as a dynamic obstacle. Agents 1 and 2 each have a starting point and a destination, and we want to find paths for both agents while ensuring they do not collide with each other or with Agent 0. We can achieve this by calling Space-Time A* twice, updating the ReservationTable between the calls:
```python
from w9_pathfinding import Grid, SpaceTimeAStar, ReservationTable
grid = Grid(width=5, height=4, edge_collision=True)
grid.add_obstacle((1, 1)) # static obstacle
path0 = [(0, 1), (0, 0), (1, 0), (2, 0), (3, 0), (3, 1)] # dynamic obstacle
start1, goal1 = (0, 2), (2, 1) # agent 1
start2, goal2 = (0, 0), (2, 0) # agent 2
rt = ReservationTable(grid)
rt.add_path(path0, reserve_destination=True)
astar = SpaceTimeAStar(grid)
path1 = astar.find_path(start1, goal1, reservation_table=rt)
rt.add_path(path1, reserve_destination=True)
path2 = astar.find_path(start2, goal2, reservation_table=rt)
print(path1) # [(0, 2), (1, 2), (2, 2), (2, 1)]
print(path2) # [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (3, 0), (2, 0)]
```
<p align="left">
<img src="https://raw.githubusercontent.com/w9PcJLyb/pathfinding/refs/heads/main/images/dynamic_obstacle_1.gif"/>
</p>
This approach works quickly and often finds reasonably good solutions. However, in some cases, it may find solutions that are far from optimal or may not find a solution at all, when one agent prevents any path for another agent. An alternative approach is to use Multi-Agent Pathfinding (MAPF) algorithms, which allow us to find paths for both agents simultaneously. Since all MAPF algorithms in this repository are designed to work with the ReservationTable, we can find an optimal solution while taking dynamic obstacles into account:
```python
from w9_pathfinding import CBS
rt = ReservationTable(grid)
rt.add_path(path0, reserve_destination=True)
cbs = CBS(grid)
paths = cbs.mapf([start1, start2], [goal1, goal2], reservation_table=rt)
print(paths[0]) # [(0, 2), (1, 2), (2, 2), (2, 2), (2, 1)]
print(paths[1]) # [(0, 0), (1, 0), (2, 0), (2, 1), (2, 0)]
```
<p align="left">
<img src="https://raw.githubusercontent.com/w9PcJLyb/pathfinding/refs/heads/main/images/dynamic_obstacle_2.gif"/>
</p>
# Types of graphs
There are several types of graphs available:
- Graph - Generic graph, directed or undirected
- Grid - Two-dimensional grid
- Grid3D - Three-dimensional grid
- HexGrid - Hexagonal grid
Any algorithm can work with any type of graph. But there are a few limitations:
1. Algorithms with a heuristic function (AStar, BiAStar, IDAStar, GBS) will work with generic graph only if coordinates are provided for each vertex. Coordinates can be added using the `set_coordinates` method.
2. An undirected generic graph does not support `edge_collision` option. You still can use MAPF algorithms with this kind of graph, but it's impossible right now to mark head to head collisions as illegal actions.
# Visualization
Visualization is only available for Grid and HexGrid. To use visualization, you need to install `matplotlib`.
Example:
```python
from w9_pathfinding import HexGrid
from w9_pathfinding.visualization import plot_grid, animate_grid
grid = HexGrid(
weights =[
[1, 1, 1, -1],
[-1, 1, 1, -1],
[1, 1, -1, -1],
[1, 1, 1, 1],
]
)
agents = [
{'start': (0, 0), 'goal': (2, 0), 'path': [(0, 0), (1, 0), (2, 0)]},
{'start': (1, 1), 'goal': (1, 0), 'path': [(1, 1), (1, 1), (1, 0)]},
]
# plot_grid returns a static image useful in the pathfinding problem
fig = plot_grid(grid, agents)
# animate_grid returns an animation useful in the mapf problem
anim = animate_grid(grid, agents)
# HTML(anim.to_html5_video()) # visualize
# anim.save("out.gif", fps=10, dpi=200) # save as a gif
```
# Installation
The easiest way to install w9-pathfinding is via pip:
```bash
pip install w9-pathfinding
```
Alternatively, you can install it manually:
1. Setup virtual environment (optional but recommended)
2. Install Cython:
```bash
pip install cython
```
3. Build the Cython extensions:
```bash
python setup.py build_ext --inplace
```
4. Finally, install the package:
```bash
pip install -e .
```
Note: If you are on Linux, you might need to install some basic build tools to compile the Cython extensions:
```bash
sudo apt install --reinstall build-essential gcc g++
```
Raw data
{
"_id": null,
"home_page": "https://github.com/w9PcJLyb/pathfinding",
"name": "w9-pathfinding",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.10",
"maintainer_email": null,
"keywords": "pathfinding mapf",
"author": "w9PcJLyb",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/58/b9/acbffcc054b2e891a6e4ed2e92b1d6fc12cc82a419ac5f7945e668037e79/w9_pathfinding-0.0.1.tar.gz",
"platform": null,
"description": "# Pathfinding\n\nPathfinding is the problem of finding the best route between two points.\n\n<p align=\"left\">\n <img src=\"https://raw.githubusercontent.com/w9PcJLyb/pathfinding/refs/heads/main/images/pf_grid.png\" width=\"128\"/>\n</p>\n\nThis repository includes several pathfinding algorithms:\n\n| Algorithm | Class name | Optimal |\n| ----------- | ----------- |----------- |\n| Depth-first search | DFS | False |\n| Best-first search | GBS | False |\n| Breadth-first search | BFS | True (only in an unweighted graph) |\n| Bidirectional Breadth-first search | BiBFS | True (only in an unweighted graph) |\n| Dijkstra | Dijkstra | True |\n| Bidirectional Dijkstra | BiDijkstra | True |\n| A* | AStar | True |\n| Bidirectional A* | BiAStar | True |\n| Iterative deepening A* | IDAStar | True |\n\nExample:\n\n```python\nfrom w9_pathfinding import Graph, Dijkstra\n\ngraph = Graph(num_vertices=4)\ngraph.add_edges(\n [\n (0, 1, 1), # start, end, cost\n (0, 2, 3),\n (0, 3, 4),\n (1, 3, 1),\n (2, 3, 1),\n ]\n)\n\ndijkstra = Dijkstra(graph)\npath = dijkstra.find_path(start=0, goal=3)\nprint(path) # [0, 1, 3]\n```\n\n# Multi-Agent Path Finding (MAPF)\n\nMulti-Agent Path Finding (MAPF) is the problem of finding collision-free paths for a group of agents from their location to an assigned target.\n\n<p align=\"left\">\n <img src=\"https://raw.githubusercontent.com/w9PcJLyb/pathfinding/refs/heads/main/images/mapf_hex.gif\"/>\n</p>\n\nImplemented algorithms:\n\n| Algorithm | Class name | Optimal | Complete |\n| ----------- | ----------- |----------- | ----------- |\n| Hierarchical Cooperative A* | HCAStar | False | False |\n| Windowed Hierarchical Cooperative A* | WHCAStar | False | False |\n| Conflict Based Search | CBS | True | True |\n| Increasing Cost Tree Search | ICTS | True (only in an unweighted graph) | True |\n| A* with Operator Decomposition | MultiAgentAStar | True | True |\n\nHere optimality means that the algorithm can find the optimal solution in terms of Sum-of-costs function.\n\nExample:\n\n```python\nfrom w9_pathfinding import Grid, WHCAStar\n\ngrid = Grid(\n # -1 - unwalkable cell\n # >= 0 - walkable, value is the cost of moving to this cell\n weights =[\n [1, 1, 1, -1],\n [-1, 1, 1, -1],\n [1, 1, -1, -1],\n [1, 1, 1, 1],\n ],\n edge_collision=True, # head to head collisions are not allowed\n)\n\nwhcastar = WHCAStar(grid)\npaths = whcastar.mapf(starts=[(0, 0), (1, 1)], goals=[(2, 0), (1, 0)])\nprint(paths) # [[(0, 0), (1, 0), (2, 0)], [(1, 1), (1, 1), (1, 0)]]\n```\n\n# Pathfinding with dynamic obstacles\n\nTo manage dynamic obstacles in pathfinding, a ReservationTable can be used. This data structure tracks the availability of each cell or edge over time, indicating whether it is free or reserved. In the case of the single-agent pathfinding problem with dynamic obstacles, there is a specialized version of the A* algorithm known as Space-Time A* (SpaceTimeAStar).\n\nLet's look at a simple example. We have three agents: Agent 0, Agent 1, and Agent 2. Agent 0 has a predetermined path that we cannot change, this agent acts as a dynamic obstacle. Agents 1 and 2 each have a starting point and a destination, and we want to find paths for both agents while ensuring they do not collide with each other or with Agent 0. We can achieve this by calling Space-Time A* twice, updating the ReservationTable between the calls:\n\n```python\nfrom w9_pathfinding import Grid, SpaceTimeAStar, ReservationTable\n\ngrid = Grid(width=5, height=4, edge_collision=True)\ngrid.add_obstacle((1, 1)) # static obstacle\n\npath0 = [(0, 1), (0, 0), (1, 0), (2, 0), (3, 0), (3, 1)] # dynamic obstacle\nstart1, goal1 = (0, 2), (2, 1) # agent 1\nstart2, goal2 = (0, 0), (2, 0) # agent 2\n\nrt = ReservationTable(grid)\nrt.add_path(path0, reserve_destination=True)\n\nastar = SpaceTimeAStar(grid)\n\npath1 = astar.find_path(start1, goal1, reservation_table=rt)\nrt.add_path(path1, reserve_destination=True)\n\npath2 = astar.find_path(start2, goal2, reservation_table=rt)\n\nprint(path1) # [(0, 2), (1, 2), (2, 2), (2, 1)]\nprint(path2) # [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (3, 0), (2, 0)]\n```\n\n<p align=\"left\">\n <img src=\"https://raw.githubusercontent.com/w9PcJLyb/pathfinding/refs/heads/main/images/dynamic_obstacle_1.gif\"/>\n</p>\n\nThis approach works quickly and often finds reasonably good solutions. However, in some cases, it may find solutions that are far from optimal or may not find a solution at all, when one agent prevents any path for another agent. An alternative approach is to use Multi-Agent Pathfinding (MAPF) algorithms, which allow us to find paths for both agents simultaneously. Since all MAPF algorithms in this repository are designed to work with the ReservationTable, we can find an optimal solution while taking dynamic obstacles into account:\n\n```python\nfrom w9_pathfinding import CBS\n\nrt = ReservationTable(grid)\nrt.add_path(path0, reserve_destination=True)\n\ncbs = CBS(grid)\npaths = cbs.mapf([start1, start2], [goal1, goal2], reservation_table=rt)\n\nprint(paths[0]) # [(0, 2), (1, 2), (2, 2), (2, 2), (2, 1)]\nprint(paths[1]) # [(0, 0), (1, 0), (2, 0), (2, 1), (2, 0)]\n```\n\n<p align=\"left\">\n <img src=\"https://raw.githubusercontent.com/w9PcJLyb/pathfinding/refs/heads/main/images/dynamic_obstacle_2.gif\"/>\n</p>\n\n# Types of graphs\n\nThere are several types of graphs available:\n\n - Graph - Generic graph, directed or undirected\n - Grid - Two-dimensional grid\n - Grid3D - Three-dimensional grid\n - HexGrid - Hexagonal grid\n\nAny algorithm can work with any type of graph. But there are a few limitations:\n\n1. Algorithms with a heuristic function (AStar, BiAStar, IDAStar, GBS) will work with generic graph only if coordinates are provided for each vertex. Coordinates can be added using the `set_coordinates` method.\n2. An undirected generic graph does not support `edge_collision` option. You still can use MAPF algorithms with this kind of graph, but it's impossible right now to mark head to head collisions as illegal actions.\n\n# Visualization\n\nVisualization is only available for Grid and HexGrid. To use visualization, you need to install `matplotlib`.\n\nExample:\n\n```python\nfrom w9_pathfinding import HexGrid\nfrom w9_pathfinding.visualization import plot_grid, animate_grid\n\ngrid = HexGrid(\n weights =[\n [1, 1, 1, -1],\n [-1, 1, 1, -1],\n [1, 1, -1, -1],\n [1, 1, 1, 1],\n ]\n)\n\nagents = [\n {'start': (0, 0), 'goal': (2, 0), 'path': [(0, 0), (1, 0), (2, 0)]},\n {'start': (1, 1), 'goal': (1, 0), 'path': [(1, 1), (1, 1), (1, 0)]},\n]\n\n# plot_grid returns a static image useful in the pathfinding problem\nfig = plot_grid(grid, agents)\n\n# animate_grid returns an animation useful in the mapf problem\nanim = animate_grid(grid, agents)\n# HTML(anim.to_html5_video()) # visualize\n# anim.save(\"out.gif\", fps=10, dpi=200) # save as a gif\n```\n\n# Installation\n\nThe easiest way to install w9-pathfinding is via pip:\n\n```bash\npip install w9-pathfinding\n```\n\nAlternatively, you can install it manually:\n\n1. Setup virtual environment (optional but recommended)\n\n2. Install Cython:\n\n ```bash\n pip install cython\n ```\n\n3. Build the Cython extensions:\n\n ```bash\n python setup.py build_ext --inplace\n ```\n\n4. Finally, install the package:\n\n ```bash\n pip install -e .\n ```\n\nNote: If you are on Linux, you might need to install some basic build tools to compile the Cython extensions:\n\n```bash\nsudo apt install --reinstall build-essential gcc g++\n```\n",
"bugtrack_url": null,
"license": "Apache-2.0",
"summary": "Implementation of some pathfinding algorithms",
"version": "0.0.1",
"project_urls": {
"Bug Tracker": "https://github.com/w9PcJLyb/pathfinding/issues",
"Homepage": "https://github.com/w9PcJLyb/pathfinding"
},
"split_keywords": [
"pathfinding",
"mapf"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "58b9acbffcc054b2e891a6e4ed2e92b1d6fc12cc82a419ac5f7945e668037e79",
"md5": "ad855353acb61c2369e38d41f6cdc851",
"sha256": "fa6fd631e824c89b66bb303090acfb3bccec2ff0f2b6c6103b781be08640cdf7"
},
"downloads": -1,
"filename": "w9_pathfinding-0.0.1.tar.gz",
"has_sig": false,
"md5_digest": "ad855353acb61c2369e38d41f6cdc851",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.10",
"size": 289559,
"upload_time": "2024-11-18T18:08:17",
"upload_time_iso_8601": "2024-11-18T18:08:17.538981Z",
"url": "https://files.pythonhosted.org/packages/58/b9/acbffcc054b2e891a6e4ed2e92b1d6fc12cc82a419ac5f7945e668037e79/w9_pathfinding-0.0.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-11-18 18:08:17",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "w9PcJLyb",
"github_project": "pathfinding",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "w9-pathfinding"
}
JSON
