Path planning

These methods find optimal paths from a start vertex to a goal vertex.

class PGraph.PGraph(arg=None, metric=None, heuristic=None, verbose=False)[source]
path_Astar(S, G, verbose=False, summary=False)[source]

A* search for path

Parameters:

  • S (Vertex subclass) – start vertex

  • G (Vertex subclass) – goal vertex

Returns:

list of vertices from S to G inclusive, path length, tree

Return type:

list of Vertex subclass, float, dict

Returns a list of vertices that form a path from vertex S to vertex G if possible, otherwise return None.

The search tree is returned as dict that maps a vertex to its parent.

The heuristic is the distance metric of the graph, which defaults to Euclidean distance.

Seealso:

heuristic()

path_BFS(S, G, verbose=False, summary=False)[source]

Breadth-first search for path

Parameters:

  • S (Vertex subclass) – start vertex

  • G (Vertex subclass) – goal vertex

Returns:

list of vertices from S to G inclusive, path length

Return type:

list of Vertex subclass, float

Returns a list of vertices that form a path from vertex S to vertex G if possible, otherwise return None.

path_UCS(S, G, verbose=False, summary=False)[source]

Uniform cost search for path

Parameters:

  • S (Vertex subclass) – start vertex

  • G (Vertex subclass) – goal vertex

Returns:

list of vertices from S to G inclusive, path length, tree

Return type:

list of Vertex subclass, float, dict

Returns a list of vertices that form a path from vertex S to vertex G if possible, otherwise return None.

The search tree is returned as dict that maps a vertex to its parent.

The heuristic is the distance metric of the graph, which defaults to Euclidean distance.