1. astar

Module for defining the classes related to the \(\mathrm{A}^\ast\) algorithm.

\(\mathrm{A}^\ast\) algorithm (pronounced as “A star”) is a search algorithm proposed in 1968 by Hart, Nilsson & Raphael (1968). It optimally finds the minimum cost path in a graph from a start node \(s\) to a goal node \(g\); in other words, the shortest path if the cost is given by its length. In addition, the algorithm does not expand as many nodes as other algorithms do; then, for a graph with a huge quantity of nodes, the computational performance is higher with respect to other search algorithms

The \(\mathrm{A}^\ast\) algorithm works constantly evaluating an evaluation function \(f(n)\) composed of two parts: one is the actual cost of the optimum path traveled from \(s\) to the current node \(n\) given by the expression \(g(n)\), and the second is the cost of the optimum path from the current node \(n\) to \(g\) given by the expression \(h(n)\), which is the heuristic component of the algorithm and it could be for example either the euclidean or manhattan distance. Thereby, the evaluation function to measure the path cost is \(f(n) = g(n) + h(n)\).

class astar.PreferredPath(coordsIdx, factor)[source]

Bases: object

Creates an instance of an object that stores the indexes of a polyline in the space of the grid-graph that represents a preferential path to be followed when the \(\mathrm{A}^\ast\) algorithm is applied.

PreferredPath(coordsIdx, factor)

The object has an attribute called factor that represents a coefficient \(k\) that multiplies the distance \(d\) between the current node \(n\) and the polyline. Considering the above, the function for evaluating the total cost of a node is modified as \(f(n) = g(n) + h(n) + kd\)

polyline

(2, n) array with the indexes of a polyline in the space of a grid-graph where the \(\mathrm{A}^\ast\) algorithm is applied. The first row corresponds to the rows and the second to the columns of the grid-graph.

Type:numpy.ndarray
factor

Multiplier of the shortest distance between the current node and the polyline.

Type:int or float

Examples

>>> from numpy import array
>>> from pybimstab.astar import PreferredPath
>>> coordsIdx = array([[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
                        13, 13, 13, 13, 13, 13, 13, 13, 13, 13],
                       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
                        2, 3, 4, 5, 6, 7, 8, 9]])
>>> preferredPath = PreferredPath(coordsIdx, factor=1)
>>> preferredPath.__dict__
{'coordsIdx': array([[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13,
                      13, 13, 13, 13, 13, 13, 13, 13, 13],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
                      2, 3, 4, 5, 6, 7, 8, 9]]),
 'factor': 1}
class astar.Node(pos, father=None, gCost=None, hCost=None, val=0)[source]

Bases: object

Creates an instance of an object that defines the structure of a node that belongs to a grid-graph where is wanted to find the optimum path through the \(\mathrm{A}^\ast\) algorithm.

Node(pos=None, father=None, gCost=None, hCost=None, val=0)
pos

Indexes of the the current node in the grid-graph.

Type:tuple
father

Indexes of the father node of the current node. Default value is None.

Type:tuple
gCost

Length of the traveled path from the start node to the current node. Default value is None.

Type:int or float
hCost

Heuristic length of the path from the current node to the goal node. Default value is None.

Type:int or float
val

Value that store the node cell in the matrix that defines the grid-graph. Default value is 0.

Type:int

Note

The class Node requires numpy and shapely

Examples

>>> node = Node(pos=(6, 7), father=(5, 7), gCost=5, hCost=10, val=1)
>>> node.__dict__
{'father': (5, 7), 'gCost': 5, 'hCost': 10, 'pos': (6, 7), 'val': 1}
getHcost(goalNode, heuristic='manhattan', preferredPath=None)[source]

Method to obtain the heuristic component, \(h(n)\), that estimates the cost (or length) of the shortest path from the current node \(n\) to the goal node.

It must be selected either manhattan or euclidean as the model to estimate the length of the optimum path.

  • manhattan is the sum of the cathetus of the right triangle defined by the current node and the goal node.
  • euclidean is the length of the hypotenuse of the right triangle defined by the current node and the goal node.

It is possible to append a polyline to force the path to follow a preferential path.

Parameters:
  • goalNode (Node object) – object with the structure of the goal node.
  • heuristic (str) – Name of the geometric model to determine the heuristic distance. It must be selected either manhattan or euclidean. The first one is the default value.
  • preferredPath (Node object) – Optional argument of the class Node to force the path. None is the default value.
Returns:

value of the estimated heuristic distance of the opmtimum path.

Return type:

(int or float)

Examples

>>> from pybimstab.astar import Node
>>> goalNode = Node(pos=(9, 9))
>>> node = Node(pos=(0, 0))
>>> node.getHcost(goalNode, heuristic='manhattan',
>>>               preferredPath=None)
18
>>> from pybimstab.astar import Node
>>> goalNode = Node(pos=(9, 9))
>>> node = Node(pos=(0, 0))
>>> node.getHcost(goalNode, heuristic='euclidean',
>>>               preferredPath=None)
12.727922061357855
getGcost(fatherNode)[source]

Method to obtain the cumulated cost \(g(n)\), of the traveled path from the start node to the current node \(n\).

Parameters:fatherNode (Node object) – object with the structure of the current node’s father.
Returns:traveled-path length from the the start node to the current node.
Return type:(int or float)

Examples

>>> from pybimstab.astar import Node
>>> node = Node(pos=(9, 9))
>>> fatherNode = Node(pos=(9, 8), gCost=15)
>>> node.getGcost(fatherNode)
16
>>> from pybimstab.astar import Node
>>> node = Node(pos=(9, 9))
>>> fatherNode = Node(pos=(8, 8), gCost=15)
>>> node.getGcost(fatherNode)
16.4142
class astar.Astar(grid, startNode, goalNode, heuristic='manhattan', reverseLeft=True, reverseUp=True, preferredPath=None)[source]

Bases: object

Creates an instance of an object that defines the optimum path into a grid-graph maze, from a start node to a goal node given.

Astar(grid, startNode, goalNode, heuristic='manhattan',
      reverseLeft=True, reverseUp=True, preferredPath=None)
gridGraph

object with the structure of maze where is wanted to find the optimum path.

Type:MazeStructure object
startNode

indexes of the gridGraph.matrix where the initial node is located. It has to be a matrix cell, ie, gridGraph.matrix[startNode]==0.

Type:tuple, list or numpy.ndarray
goalNode

indexes of the gridGraph.matrix where the ending node is located. It has to be a matrix cell, ie, gridGraph.matrix[goalNode]==0.

Type:tuple, list or numpy.ndarray
heuristic

Name of the geometric model to determine the heuristic distance. It must be selected either manhattan or euclidean. The first one is the default value.

Type:str
reverseLeft

Logical variable to allow or not reverses movements to the left. Default value is True.

Type:bool
reverseUp

Logical variable to allow or not reverses movements to upward. Default value is True.

Type:bool
*forcedPath

Optional aguments to force the optimum path close to a specific polyline.

Type:PreferredPath object

Note

The class Astar requires NumPy and Matplotlib.

Examples

>>> from numpy import array
>>> from pybimstab.astar import PreferredPath, Astar
>>> grid = array([[ 0,  0,  0,  0,  1,  0,  0,  0,  0,  0],
>>>               [ 0,  0,  0,  0,  1,  1,  0,  0,  0,  0],
>>>               [ 0,  0,  0,  1,  1,  0,  1,  0,  1,  0],
>>>               [ 0,  1,  1,  0,  0,  0,  0,  1,  0,  0],
>>>               [ 0,  0,  0,  1,  0,  0,  0,  1,  1,  1],
>>>               [ 0,  0,  1,  0,  1,  1,  0,  0,  0,  0],
>>>               [ 0,  0,  1,  0,  1,  0,  1,  0,  0,  0],
>>>               [ 1,  1,  0,  1,  0,  0,  0,  0,  1,  1],
>>>               [ 1,  0,  0,  0,  0,  0,  0,  0,  0,  0],
>>>               [ 0,  0,  0,  0,  1,  0,  1,  0,  0,  1],
>>>               [ 0,  1,  0,  0,  0,  1,  0,  0,  0,  0],
>>>               [ 1,  0,  0,  0,  0,  0,  0,  0,  0,  0],
>>>               [ 0,  0,  0,  0,  0,  0,  0,  0,  1,  0],
>>>               [ 1,  0,  0,  0,  1,  0,  0,  0,  0,  0]
>>>               ])
>>> coordsIdx = array([[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
>>>                     13, 13, 13, 13, 13, 13, 13, 13, 13, 13],
>>>                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
>>>                     2, 3, 4, 5, 6, 7, 8, 9]])
>>> preferredPath = PreferredPath(coordsIdx, factor=1)
>>> astar = Astar(grid, startNode=(0, 0), goalNode=(13, 9),
>>>               heuristic='manhattan', reverseLeft=True,
>>>               reverseUp=True, preferredPath=preferredPath)
>>> astar.__dict__.keys()
dict_keys(['grid', 'startNode', 'goalNode', 'heuristic', 'reverseLeft',
           'reverseUp', 'preferredPath', 'mazeStr', 'optimumPath'])
defineMazeStr()[source]

Defines the clean structure of the grid-graph using objects instaced from the class Node for each node (or cell of the grid).

Those cells with value equal to one or minus one will have a g-value equal to infinite because over those cells, a path is impossible to be traced.

Returns:array with the same shape of the input grid where each cell is an object from the class Node with the structure of its respective node.
Return type:(numpy.ndarray)

Examples

>>> # after executing the example of the class
>>> astar.mazeStr[0, 0].__dict__
{'father': (0, 0), 'gCost': 0, 'hCost': 22.0, 'pos': (0, 0),
 'val': 0}
getNeighbours(node)[source]

Method for obtaining the possible neighbours of an specific node that belongs to the grid given.

Each neighbour is given as a tuple with the indexes of the grid.

Parameters:node (Node object) – object with the structure of the node which is wanted to know its possible neighbours.
Returns:Tuples with the indexes of possible neighbours of the node in question.
Return type:(list)

Examples

>>> # after executing the example of the class
>>> from pybimstab.astar import Node
>>> astar.getNeighbours(Node(pos=(1, 1)))
[(0, 1), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0), (1, 0), (0, 0)]
>>> astar.getNeighbours(Node(pos=(0, 0)))
[(0, 1), (1, 1), (1, 0)]
>>> astar.getNeighbours(Node(pos=(0, 1)))
[(0, 2), (1, 2), (1, 1), (1, 0), (0, 0)]
>>> astar.getNeighbours(Node(pos=(0, 2)))
[(1, 2), (1, 1), (0, 1)]
>>> astar.getNeighbours(Node(pos=(1, 2)))
[(0, 2), (2, 2), (2, 1), (1, 1), (0, 1)]
>>> astar.getNeighbours(Node(pos=(2, 2)))
[(1, 2), (2, 1), (1, 1)]
>>> astar.getNeighbours(Node(pos=(2, 1)))
[(1, 1), (1, 2), (2, 2), (2, 0), (1, 0)]
>>> astar.getNeighbours(Node(pos=(2, 0)))
[(1, 0), (1, 1), (2, 1)]
>>> astar.getNeighbours(Node(pos=(1, 0)))
[(0, 0), (0, 1), (1, 1), (2, 1), (2, 0)]
getWayBack(node)[source]

Method for obtaining the whole way back of an specific node which has been opened by the A star algorithm.

Parameters:node (Node object) – object with the structure of the node which is wanted to know its way back.
Returns:\(\left(2 \times n \right)\) array where \(n\) is the number of nodes where the path has crossed; the first row of the array contains the abscisses and the second one contains the ordinates of the nodes into the grid-graph
Return type:(numpy.ndarray)

Examples

>>> import numpy as np
>>> from pybimstab.astar import PreferredPath, Node, Astar
>>> grid = np.zeros((3,3))
>>> grid[1:3, 0:2] = 1
>>> astar = Astar(grid, startNode=(0, 0), goalNode=(2, 2),
>>>               heuristic='manhattan', reverseLeft=True,
>>>               reverseUp=True, preferredPath=None)
>>> # returning the way back
>>> astar.getWayBack(astar.mazeStr[2, 2])
array([[2, 1, 0, 0],
       [2, 1, 1, 0]])
>>> astar.getWayBack(astar.mazeStr[1, 2])
array([[1, 0, 0],
       [2, 1, 0]])
>>> astar.getWayBack(astar.mazeStr[1, 1])
ValueError: Input node is a block. It doesn't have a wayback
getPath()[source]

Method for obtaining the optimum path between two points into a grid-graph through the \(\mathrm{A}^\ast\) algorithm Hart, Nilsson & Raphael (1968).

Returns:\(\left(2 \times n \right)\) array where \(n\) is the number of nodes where the path has crossed; the first row of the array contains the abscisses and the second one contains the ordinates of the nodes into the grid-graph
Return type:(numpy.ndarray)

Examples

>>> from numpy import array
>>> from pybimstab.astar import PreferredPath, Astar
>>> grid = array([[ 0,  0,  0,  0,  1,  0,  0,  0,  0,  0],
>>>               [ 0,  0,  0,  0,  1,  1,  0,  0,  0,  0],
>>>               [ 0,  0,  0,  1,  1,  0,  1,  0,  1,  0],
>>>               [ 0,  1,  1,  0,  0,  0,  0,  1,  0,  0],
>>>               [ 0,  0,  0,  1,  0,  0,  0,  1,  1,  1],
>>>               [ 0,  0,  1,  0,  1,  1,  0,  0,  0,  0],
>>>               [ 0,  0,  1,  0,  1,  0,  1,  0,  0,  0],
>>>               [ 1,  1,  0,  1,  0,  0,  0,  0,  1,  1],
>>>               [ 1,  0,  0,  0,  0,  0,  0,  0,  0,  0],
>>>               [ 0,  0,  0,  0,  1,  0,  1,  0,  0,  1],
>>>               [ 0,  1,  0,  0,  0,  1,  0,  0,  0,  0],
>>>               [ 1,  0,  0,  0,  0,  0,  0,  0,  0,  0],
>>>               [ 0,  0,  0,  0,  0,  0,  0,  0,  1,  0],
>>>               [ 1,  0,  0,  0,  1,  0,  0,  0,  0,  0]
>>>               ])
>>> coordsIdx = array(
>>>     [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 13, 13,
>>>       13, 13, 13, 13, 13, 13, 13],
>>>      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4,
>>>       5, 6, 7, 8, 9]])
>>> preferredPath = PreferredPath(coordsIdx, factor=1)
>>> # without a forced path
>>> astar = Astar(grid, startNode=(0, 0), goalNode=(13, 9),
>>>               heuristic='manhattan', reverseLeft=True,
>>>               reverseUp=True, preferredPath=None)
>>> astar.getPath()
array(
    [[13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  4,  3,  2,  1,  0],
     [ 9,  9,  9,  9,  8,  8,  7,  7,  6,  5,  4,  3,  2,  1,  0]])
>>> # with a forced path
>>> astar = Astar(grid, startNode=(0, 0), goalNode=(13, 9),
>>>               heuristic='manhattan', reverseLeft=True,
>>>               reverseUp=True, preferredPath=preferredPath)
>>> astar.getPath()
array([
    [13, 13, 13, 13, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
    [ 9, 8, 7, 6, 5, 4,  3, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0]])
>>> from numpy import array
>>> from pybimstab.astar import PreferredPath, Astar
>>> grid = array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 1, 0, 0, 1, 1, 0, 0],
                  [1, 1, 0, 0, 1, 0, 1, 0, 0, 0],
                  [0, 0, 0, 1, 1, 0, 1, 0, 0, 1],
                  [0, 0, 1, 1, 0, 1, 1, 1, 0, 0],
                  [0, 0, 0, 1, 1, 0, 1, 0, 0, 1],
                  [0, 0, 0, 0, 1, 0, 0, 1, 0, 0],
                  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
                  [0, 0, 1, 0, 0, 1, 0, 0, 0, 0]])
>>> astar = Astar(grid, startNode=(0, 0), goalNode=(9, 9),
>>>               heuristic='manhattan', reverseLeft=True,
>>>               reverseUp=True, preferredPath=None)
>>> astar.getPath()
array([[9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [9, 8, 8, 8, 8, 8, 8, 8, 8, 7, 6, 5, 4, 3, 2, 1, 0]])
>>> astar = Astar(grid, startNode=(0, 0), goalNode=(9, 9),
>>>               heuristic='euclidean', reverseLeft=True,
>>>               reverseUp=True, preferredPath=None)
>>> astar.getPath()
array([[9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0],
       [9, 8, 7, 6, 5, 4, 5, 5, 4, 3, 2, 1, 0]])
plot(plotPreferredPath=False)[source]

Method for generating a graphic of the optimum path returned from the astar method.

Parameters:plotForcedPath (bool) – logical variable to check if the forced path exists and is wanted to plot.
Returns:object with the matplotlib structure of the plot. You might use it to save the figure for example.
Return type:(matplotlib.figure.Figure)

Examples

>>> from numpy import array
>>> from pybimstab.astar import PreferredPath, Astar
>>> grid = array([[0,  0,  0,  0,  1,  0,  0,  0,  0,  0],
>>>               [0,  0,  0,  0,  1,  1,  0,  0,  0,  0],
>>>               [0,  0,  0,  1,  1,  0,  1,  0,  1,  0],
>>>               [0,  1,  1,  0,  0,  0,  0,  1,  0,  0],
>>>               [0,  0,  0,  1,  0,  0,  0,  1,  1,  1],
>>>               [0,  0,  1,  0,  1,  1,  0,  0,  0,  0],
>>>               [0,  0,  1,  0,  1,  0,  1,  0,  0,  0],
>>>               [1,  1,  0,  1,  0,  0,  0,  0,  1,  1],
>>>               [1,  0,  0,  0,  0,  0,  0,  0,  0,  0],
>>>               [0,  0,  0,  0,  1,  0,  1,  0,  0,  1],
>>>               [0,  1,  0,  0,  0,  1,  0,  0,  0,  0],
>>>               [1,  0,  0,  0,  0,  0,  0,  0,  0,  0],
>>>               [0,  0,  0,  0,  0,  0,  0,  0,  1,  0],
>>>               [1,  0,  0,  0,  1,  0,  0,  0,  0,  0]
>>>               ])
>>> coordsIdx = array(
>>>     [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 13, 13,
>>>       13, 13, 13, 13, 13, 13, 13],
>>>      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4,
>>>       5, 6, 7, 8, 9]])
>>> preferredPath = PreferredPath(coordsIdx, factor=1)
>>> for typePP in [None, preferredPath]:
>>>     astar = Astar(grid, startNode=(0, 0), goalNode=(13, 9),
>>>                   heuristic='manhattan', reverseLeft=True,
>>>                   reverseUp=True, preferredPath=typePP)
>>>     fig = astar.plot(plotPreferredPath=True)
astar_example1b
astar_example1a

example script.

>>> from numpy import array
>>> from pybimstab.astar import Astar
>>> grid = array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 1, 0, 0, 1, 1, 0, 0],
                  [1, 1, 0, 0, 1, 0, 1, 0, 0, 0],
                  [0, 0, 0, 1, 1, 0, 1, 0, 0, 1],
                  [0, 0, 1, 1, 0, 1, 1, 1, 0, 0],
                  [0, 0, 0, 1, 1, 0, 1, 0, 0, 1],
                  [0, 0, 0, 0, 1, 0, 0, 1, 0, 0],
                  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
                  [0, 0, 1, 0, 0, 1, 0, 0, 0, 0]])
>>> for heuristic in ['manhattan', 'euclidean']:
>>>     astar = Astar(grid, startNode=(0, 0), goalNode=(9, 9),
>>>                   heuristic=heuristic, reverseLeft=True,
>>>                   reverseUp=True, preferredPath=None)
>>>     fig = astar.plot()
astar_example1b
astar_example2a

example script.

>>> from numpy import array
>>> from pybimstab.bim import BlocksInMatrix
>>> from pybimstab.astar import Astar
>>> seed = 111  # for repeatibilty
>>> boundary = array([[-5, 0, 5, 0, -5], [0, 10, 0, -10, 0]])
>>> bim = BlocksInMatrix(slopeCoords=boundary, blockProp=0.2,
>>>                      tileSize=0.4, seed=seed)
>>> astar = Astar(bim.grid, startNode=(0, 12), goalNode=(49, 12),
>>>               heuristic='manhattan', reverseLeft=True,
>>>               reverseUp=True, preferredPath=None)
>>> fig = astar.plot()
astar_example3

example script.