Warning

This page is located in archive.

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).

Due date | December 17, 2023, 23:59 PST |

Deadline | January 13, 2024, 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: 2023/09/25 11:03 by pragrmi1