BiRRT

class discopygal.solvers.rrt.birrt.BiRRT(num_landmarks, eta, n_join, bounding_margin_width_factor=2, nearest_neighbors_start=None, nearest_neighbors_end=None, metric=None, sampler=None)

Bases: Solver

Implementation of the BiRRT algorithm. We grow two trees - one rooted at start, the other at the end. Every once in a while (n_join) try to extend both trees toward the same sample. Supports multi-robot motion planning, though might be inefficient for more than two-three robots.

Parameters:

  • num_landmarks (int) – number of landmarks to sample

  • eta (FT) – maximum distance when steering

  • n_join (int) – period of iterations when trying to grow the trees towards the same sample

  • nearest_neighbors_start (NearestNeighbors or None) – a nearest neighbors algorithm for the tree grown from start. if None then use sklearn implementation

  • nearest_neighbors_end (NearestNeighbors or None) – a nearest neighbors algorithm for the tree grown from end. if None then use sklearn implementation

  • metric (Metric or None) – a metric for weighing edges, can be different then the nearest_neighbors metric! If None then use euclidean metric

  • sampler (Sampler) – sampling algorithm/method. if None then use uniform sampling

collision_free(p, q)

Get two points in the configuration space and decide if they can be connected

static from_arguments(d)

Get a dictionary of arguments and return a solver. Should be overridded by solvers.

Parameters:

d (dict) – arguments dict

static get_arguments()

Return a list of arguments and their description, defaults and types. Can be used by a GUI to generate fields dynamically. Should be overridded by solvers.

Returns:

arguments dict

Return type:

dict

get_graph()

Return a graph (if applicable). Can be overridded by solvers.

Returns:

graph whose vertices are Point_2 or Point_d

Return type:

networkx.Graph or None

load_scene(scene)

Load a scene into the solver. Derived solvers can override this method to also add some sort of pre-processing to the scene

Parameters:

scene (Scene) – scene to load

sample_free()

Sample a free random point

solve()

Based on the start and end locations of each robot, solve the scene (i.e. return paths for all the robots)

Returns:

path collection of motion planning

Return type:

PathCollection

steer(p_near, p_rand, eta)

Steer in eta units from p_near towards p_rand