Rapidly Exploring Random Tree¶
Construction of the Rapidely Exploring Random Tree
-
class
rrt.Edge(node_from, node_to, path, cost)[source]¶ Edge of the rapidly exploring random tree.
Attributes: - node_from : tuple
Id of the starting node of the edge.
- node_to : tuple
Id of the end node of the edge.
- path : list
The successive positions yielded by the local planner representing the path between the nodes.
- cost : float
Cost associated to the transition between the two nodes.
-
class
rrt.Node(position, time, cost)[source]¶ Node of the rapidly exploring random tree.
Attributes: - destination_list : list
The reachable nodes from the current one.
- position : tuple
The position of the node.
- time : float
The instant at which this node is reached.
- cost : float
The cost needed to reach this node.
-
class
rrt.RRT(environment, precision=(5, 5, 1))[source]¶ Class implementing a Rapidely Exploring Random Tree in two dimensions using dubins paths as an expansion method. The state space considered here is straightforward, as every state can be represented by a simple tuple made of three continuous variables: (x, y, psi)
Attributes: - nodes : dict
Dictionnary containing all the nodes of the tree. The keys are hence simply the reached state, i.e. tuples of the form (x, y, psi).
- environment : Environment
Instance of the Environment class.
- goal_rate : float
The frequency at which the randomly selected node is choosen among the goal zone.
- precision : tuple
The precision needed to stop the algorithm. In the form (delta_x, delta_y, delta_psi).
- goal : tuple
The position of the goal (the center of the goal zone), in the form of a tuple (x, y, psi).
- root : tuple
The position of the root of the tree, (the initial position of the vehicle), in the form of a tuple (x, y, psi).
- local_planner : Planner
The planner used for the expansion of the tree, here it is a Dubins path planner.
Methods
in_goal_region(sample)Method to determine if a point is within a goal region or not. run(goal[, nb_iteration, goal_rate, metric])Executes the algorithm with an empty graph, initialized with the start position at least. select_options(sample, nb_options[, metric])Chooses the best nodes for the expansion of the tree, and returns them in a list ordered by increasing cost. plot_tree Displays the RRT using matplotlib. -
children_count(node)[source]¶ Not optimal at all as it recounts a lot of the tree every time a path needs to b selected.
-
in_goal_region(sample)[source]¶ Method to determine if a point is within a goal region or not.
Parameters: - sample : tuple
(x, y, psi) the position of the point which needs to be tested.
-
plot(file_name='', close=False, nodes=False)[source]¶ Displays the tree using matplotlib, on a currently open figure.
Parameters: - file_name : string
The name of the file used to save an image of the tree.
- close : bool
If the plot needs to be automaticaly closed after the drawing.
- nodes : bool
If the nodes need to be displayed as well.
-
run(goal, nb_iteration=100, goal_rate=0.1, metric='local')[source]¶ Executes the algorithm with an empty graph, initialized with the start position at least.
Parameters: - goal : tuple
The final requested position (x, y, psi).
- nb_iteration : int
The number of maximal iterations (not using the number of nodes as potentialy the start is in a region of unavoidable collision).
- goal_rate : float
The probability to expand towards the goal rather than towards a randomly selected sample.
- metric : string
One of ‘local’ or ‘euclidian’. The method used to select the closest node on the tree from which a path will be grown towards a sample.
Notes
It is not necessary to use several nodes to try and connect a sample to the existing graph; The closest node only could be choosen. The notion of “closest” can also be simpy the euclidian distance, which would make the computation faster and the code a simpler, this is why several metrics are available.
-
select_best_edge()[source]¶ Selects the best edge of the tree among the ones leaving from the root. Uses the number of children to determine the best option.
Returns: - edge :Edge
The best edge.
-
select_options(sample, nb_options, metric='local')[source]¶ Chooses the best nodes for the expansion of the tree, and returns them in a list ordered by increasing cost.
Parameters: - sample : tuple
The (x, y, psi) coordinates of the node we wish to connect to the tree.
- nb_options : int
The number of options requested.
- metric : str
One of ‘local’, ‘euclidian’. The euclidian metric is a lot faster but is also less precise and can’t be used with an RRT star.
Returns: - options : list
Sorted list of the options, by increasing cost.
