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 |
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 init
sets the environment by arguments:
environment
- Environment - geometric representation of the environment and robot together with the wrapper for RAPID collision checking library,
environment.check_robot_collision(P)
where P
is Pose
message. Returns True
if the Robot at pose P
collides with the obstacle,
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 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:
None
when the path cannot be found. The individual poses of the path shall not be further than collision_step
.
Steer
function.
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