AStarSearch.jl
A* Algorithm in Julia.
This module exports the astar
function that provides a generic implementation of the algorithm.
The type of the state is totally unrestricted, just provide the functions that give neighbour states and an heuristic given a state and the algorithm will find the best path.
To ease the definition of more complex problems in which you usually want to search from the best path from start to end, given also some parameters from the problem instance, the AbstractAStarSearch
type is introduced. You should define the neighbour function heuristic on the instance of your concrete AStarSearch type, with also that type in the signature, and then use the search
function on that problem instance, given the start and goal state.
Installation
In the Julia Pkg REPL, type: add AStarSearch
Usage
astar(start, isgoal, getneighbours, heuristic; cost = defaultcost, timeout = Inf, hashfn = defaulthash, maxcost = Inf, maxdepth = Inf)
Execute the A* algorithm to get the best path from the start state to reach a goal condition. Only the first 4 arguments are mandatory, all the others are optional.
Result
It returns a structure in which the status
field is a Symbol that can be either:
:success
: the algorithm found a path from start to goal:timeout
: the algorithm timed out, a partial path to the best state is returned in thepath
field:nopath
: the algorithm didn't find any path to a goal, the path to the best state is still returned
The other fields are:
path
: an array of states from the start state to the goal or the best found statecost
: the cost of the returned pathclosedsetsize
: how many states the algorithm tested if they were a goal (size of the closed set)opensetsize
: how many states were still in the open set when the algorithm ended
Arguments
start
: the starting state, the type of the state is completely unrestrictedisgoal
: a function to evaluate if a state satisfies a goal conditiongetneighbours
: a function that takes a state and returns the neighbour states as an array (or iterable)heuristic
: a function that given a state returns an estimate of the cost to reach goal. This estimate should be optimistic if you want to be sure to get the best path. Notice that the best path could be very expensive to find, so if you want a good but not guaranteed optimal path, you could multiply your heuristic by a constant, the algorithm will usually be much fastercost
: a function that takes the current state and a neighbour and returns the cost to do that state transition. By default all transitions cost 1timeout
: timeout in number of seconds after which the algorithm stops returning the best partial path to the state with the lowest heuristic, by default it is unrestricted. Please notice that the algorithm wil run AT LEAST the specified time.hashfn
: a function that takes a state and returns a compact representation to use as dictionary key (usually one of UInt, Int, String), by default it is just the identity function as the state is used directly as key. This is a very important field for composite states in order to avoid duplicationsmaxcost
: a maximum bound of the accumulated cost of the path, this can result in a :nopath result even if a path to the goal (with a greater cost) exists. By default it is Infmaxdepth
: the maximum depth the algorithm is allowed to go down while expanding the search state, the same considerations as themaxcost
parameter apply. By default it is Inf
AbstractAStarSearch
Abstract Type that can be subtyped by concrete structures that represent a parametrizable problem.
Define a structure as subtype of AbstractAStarSearch, then you have to define:
neighbours(astarsearch::YourAStarSearchStruct{YourStateType}, current::YourStateType)
-> returns an array of neighbour statesheuristic(astarsearch::YourAStarSearchStruct{YourStateType}, current::YourStateType, goal::YourStateType)
-> returns an estimate of the cost to get to the end
And optionally you can redefine:
isgoal(astarsearch::YourAStarSearchStruct{YourStateType}, current::YourStateType, goal::YourStateType)
-> returns bool (by default it's current == goal)cost(astarsearch::YourAStarSearchStruct{YourStateType}, current::YourStateType, neighbour::YourStateType)
-> returns the cost between the current state and a neighbour (by default = 1)
Then you can find the optimal path with:
search(aastarsearch::YourAStarSearchStruct{YourStateType}, start::YourStateType, goal::YourStateType; timeout = Inf, maxcost = Inf, maxdepth = Inf)
The other optional parameters are documented in the astar
function above.
Examples
It's a very general algorithm so you can solve shortest paths in mazes but also all sorts of puzzles such as the 15 Puzzle.
Both the maze example and the 15 Puzzle solver are in the test
folder.
If you want to find the best path in a maze using the manhattan heuristic you can do the following:
using Test
using AStarSearch
# Directions are seen as cartesian indexes so that they can be added to a position to get the next position
UP = CartesianIndex(-1, 0)
DOWN = CartesianIndex(1, 0)
LEFT = CartesianIndex(0, -1)
RIGHT = CartesianIndex(0, 1)
DIRECTIONS = [UP, DOWN, LEFT, RIGHT]
# manhattan distance between positions in the maze matrix
manhattan(a::CartesianIndex, b::CartesianIndex) = sum(abs.((b - a).I))
# check to be in the maze and filter out moves that go into walls
getmazeneighbours(maze, state) = filter(x -> (1 <= x[1] <= size(maze)[1]) && (1 <= x[2] <= size(maze)[2]) && (!maze[x]), [state + d for d in DIRECTIONS])
# 0 = free cell, 1 = wall
maze = [0 0 1 0 0;
0 1 0 0 0;
0 1 0 0 1;
0 0 0 1 1;
1 0 1 0 0] .== 1
start = CartesianIndex(1, 1)
goal = CartesianIndex(1, 5)
isgoal(state) = state == goal
getneighbours(state) = getmazeneighbours(maze, state)
mazeheuristic(state) = manhattan(state, goal)
res = astar(start, isgoal, getneighbours, mazeheuristic)
@test res.status == :success
@test res.path == CartesianIndex{2}[
CartesianIndex(1, 1),
CartesianIndex(2, 1),
CartesianIndex(3, 1),
CartesianIndex(4, 1),
CartesianIndex(4, 2),
CartesianIndex(4, 3),
CartesianIndex(3, 3),
CartesianIndex(2, 3),
CartesianIndex(2, 4),
CartesianIndex(1, 4),
CartesianIndex(1, 5)]
@test res.cost == 10
Maze Example by subtyping AbstractAStar
Given that manhattan
and getmazeneighbours
are defined as above, you can design the same solution like this:
import AStarSearch: neighbours, heuristic
struct MazeSolver <: AbstractAStarSearch{CartesianIndex{2}}
maze:: BitArray{2}
end
neighbours(ms::MazeSolver, state::CartesianIndex{2}) = getmazeneighbours(ms.maze, state)
heuristic(ms::MazeSolver, state::CartesianIndex{2}, goal::CartesianIndex{2}) = manhattan(state, goal)
# 0 = free cell, 1 = wall
maze = [0 0 1 0 0;
0 1 0 0 0;
0 1 0 0 1;
0 0 0 1 1;
1 0 1 0 0] .== 1
mz = MazeSolver(maze)
start = CartesianIndex(1, 1)
goal = CartesianIndex(1, 5)
res = search(mz, start, goal)
The same results like above are returned.
Breaking Changes
0.3.0
The 0.3.0 release introduces a more strict type checking, requiring uniformity of types between the cost and the heuristics, to improve performance.
If you get type errors, it will probably be because by default the cost is Int64, and you provided a Float heuristic.
You can either provide the cost function that returns a float, or cast the heuristic to Int64.