Warning

This page is located in archive.
Go to the latest version of this course pages.
Go the latest version of this page.

The main task is to learn the basic principles of randomized sampling-based planning. The principles are demonstrated on the multi-query planning algorithm - Rapidly-exploring Random Trees (RRT).

Deadline | December 12, 2020, 23:59 PST |

Points | 7 |

Label in BRUTE | t3b-rrt |

Files to submit | archive with the `RRTPlanner.py` file |

Resources | B4M36UIR_t3_resource_pack |

- Compile rapid library by
`make`

in`environment/rapid`

library.

In class `RRTPlanner.py`

implement RRT/RRT* algorithm according to the description and pseudo-code from [1].

**Initialization** of `RRTPlanner`

class by method

sets the environment by arguments:
*init*

`environment`

- Environment - geometric representation of the environment and robot together with the wrapper for RAPID collision checking library,- represents robot and environment,
- check for collision between the robot and the environment using function
`environment.check_robot_collision(P)`

where`P`

is`Pose`

message. Returns`True`

if the Robot at pose`P`

collides with the obstacle, - contains environment dimensions in
`environment.limits_x`

,`environment.limits_y`

,`environment.limits_z`

float constants.

`translate_speed`

: Speed of translation motion [m/s].`rotate_speed`

Angular speed of rotation motion [rad/s].

The RRT/RRT* algorithm itself is divided into two methods `expand_tree`

and `query`

. Thus, we implement multi-query variant of the RRT/RRT* algorithm.

**First method** `expand_tree`

is called to build the tree and return it as a `NavGraph`

structure. The input parameters are:

`start`

- Pose message - the start pose of the robot.`space`

- Type of configuration space (“R2”, “SE(2)”, “R3”, “SE(3)”).`number_of_samples`

- Number of samples to be generated.`neighborhood_radius`

- Neighborhood radius to connect samples [s].`collision_step`

- Minimum step to check collisions [s].`isrrtstar`

- Determine variant of the algorithm (`False`

→ RRT,`True`

→ RRT*).`steer_step`

- Step utilized of steering function [s].

Returns:

- the NavGraph message representing the underlying navigation graph constructed by the method from which the resulting path is reconstructed.

**The second method** `query`

retrieves a path from the expanded tree. The input parameters of the function are:

`goal`

- Pose message - the desired goal pose of the robot.`neighborhood_radius`

- Neighborhood radius to connect samples [s].`collision_step`

- Minimum step to check collisions [s].`isrrtstar`

- Determine variant of the algorithm (`False`

→ RRT,`True`

→ RRT*).

Returns:

- the Path message with the found path or
`None`

when the path cannot be found. The individual poses of the path shall not be further than`collision_step`

.

- You can use provided
`Steer`

function. - Use tree structure for RRT/RRT* instead of a general graph.
- There are two ways how to store cost in tree nodes:
- Store the total cost.
- Store cost of the last connection.

- Use
`neighborhood_radius`

in`Near`

function.

RRT algorithm in “R2” space with 300 (left) and 1000 (right) samples.

RRT* algorithm in “R2” space with 300 (left) and 1000 (right) samples.

[1] Karaman, Sertac, and Emilio Frazzoli. “Sampling-based algorithms for optimal motion planning.” The international journal of robotics research 30.7 (2011): 846-894. Journal version Arxiv version

courses/uir/hw/t3b-rrt.txt · Last modified: 2021/09/14 17:28 by pragrmi1