This repository is just a compilation of each assignment from the 2021/2 EEE935 class. It includes the following motion planning algorithms using ROS + Python: Tangent Bug, a Path Following, a simple Potential Function, Wave-Front, A*, a sensor-based GVD, a coverage algorithm and a RRT planner. For each one of these, the robot is non-holonomic and a velocity controller is used with feedback linearization. Stage simulator is used for every algorithm. Every algorithm was implemented as given in Choset, Lynch, and Hutchinson1.
The description of the assignments are in the TPs folder.
The path following algorithm works by following a list of time-independent coordinates. The Potential Function algorithm uses simple repulsive and attractive potentials. The Wave Front algorithm accepts 4 and 8 point connectivity. The A* generates the graph in real-time based on a premade grid. The incomplete GVD algorithm generates a Generalized Voronoi Diagram (GVD) based on sensor readings. The Coverage algorithm depends on a premade trapezoidal cell decomposition and, based on a list of cells (Cell class as defined in its script), covers the whole map. The RRT algorithm uses a bidirectional RRT based on a grid. Every grid used has the obstacles expanded in order to treat the robot as a point.
 |
 |
|---|---|
| Tangent Bug | Path(different rotation bias) |
 |
 |
|---|---|
| Path Following | Path |
 |
 |
|---|---|
| Potential Function | Path (2nd) |
 |
 |
|---|---|
| Wave Front | Wavefront Grid (8 neighbors) |
 |
 |
|---|---|
| A* | Path |
 |
 |
|---|---|
| RRT | Path + Trees |
 |
 |
|---|---|
| Coverage | Path + Cell decomposition |
 |
 |
|---|---|
| GVD | Resulting GVD |
The python scripts for Tangent Bug, Potential Function, Wave-Front, A* and RRT algorithms assume the existence of two robots in Stage simulator/.world file, the first, green square, robot being the robot to be controlled and the second, orange square, a representation of the goal. So if any other map is used and it does not have two objects in this specific order, then the rospy Publishers and Subscribers for each one of these python scripts should be changed.
Path Following, Wave-Front, A*, Coverage and RRT behavior will not change if only the map is changed as they have internal parameters in respect to the default map.
By default it is assumed that the map is empty.world. If any other map is used, the user must edit its launch file, if you are not going to run it manually.
Running with the default map and parameters implies that the goal, the orange square, is set to (4, 2) and the initial robot position is set to (-6, 2). When this goal is reached, it's possible to move the robot with the mouse and rerun the algorithm, such that the robot can converge to the same goal from a different initial position.
The algorithm should recognize that it is impossible to reach the goal in some scenarios. For testing this behavior goal:="0 -11" is a recommended parameter. The are cases where the algorithm doesn't behave properly, so this goal position and robot's default initial position guarantee that it will work prperly.
It's possible to run the Tangent Bug algorithm using its launch file. There is a optional argument goal that corresponds to the coordinates of the goal in meters as "x_goal y_goal", by default goal:="4 2".
To run with default parameters, simply run in terminal:
roslaunch potential_function potential_function.launchTo run with different parameters:
roslaunch potential_function potential_function.launch goal:="0 -10"In one terminal run:
roscd tangent_bug
rosrun stage_ros stageros worlds/maze.world In another terminal run:
rosrun tangent_bug tangent_bug_alg.py x ywhere x is the goal x-coordinate, y is the goal y-coordinate.
By default it is assumed that the map is empty.world. If any other map is used, the user must edit its launch file, if you are not going to run it manually.
The default map implies that the path to be followed is a Rhodonea curve given with 6 petals.
It's possible to run the Path Following algorithm using its launch file.
Simply run in terminal:
roslaunch path_following path_following.launchIn one terminal run:
roscd path_following
rosrun stage_ros stageros worlds/empty.world In another terminal run:
rosrun path_following path_following.pyBy default it is assumed that the map is maze.world. If any other map is used, the user must edit its launch file, if you are not going to run it manually.
Running with the default map and parameters implies that the goal, the orange square, is set to (5, 2) and the initial robot position is set to (-2, -4). When this goal is reached, it's possible to move the robot with the mouse and rerun the algorithm, such that the robot can converge to the same goal from a different initial position.
It's possible to run the Potential Function algorithm using its launch file. There is a optional argument goal that corresponds to the coordinates of the goal in meters as "x_goal y_goal", by default goal:="5 2".
To run with default parameters, simply run in terminal:
roslaunch potential_function potential_function.launchTo run with different parameters:
roslaunch potential_function potential_function.launch goal:="-6 -2"In one terminal run:
roscd potential_function
rosrun stage_ros stageros worlds/maze.world In another terminal run:
rosrun potential_function potential_function.py x ywhere x is the goal x-coordinate, y is the goal y-coordinate.
The Wave-Front algorithm depends on a pre-made grid that corresponds to the configuration space of a map. This grid is a binary matrix, where 0s correspond to free space and 1s correspond to obstacles. It then computes the planner grid as in Choset, Lynch, and Hutchinson1, using 4 or 8 point connectivity. Robot motion is then based on the generated planner grid.
By default it is assumed that the map is maze.world and its respective configuration space grid grid1.npy. If any other map is used, the user must edit wavefront.py with the respective Stage parameters and configuration space grid (.npy file). If the launch file is used, the user should change its .world file.
To create configuration space grids for other maps, you can use the map_expander.py script changing the parameters as necessary.
The robot's initial position must be set on wavefront.py. When this algorithm is run with the default map the green square represents the robot and the orange square represents the goal at the default position, i.e. (5, 2).
It's possible to run the Wave-Front planner using its launch file. There are two optional arguments goal and neighbors. goal are the coordinates of the goal in meters as "x_goal y_goal", and neighbors is the number of connectivity points to use when creating the Wave-Front grid, its value can be either 4 or 8 (if any other integer is passed, 8 is assumed).
The default arguments are goal:="5 2" and neighbors:="4".
To run with default parameters, simply run in terminal:
roslaunch wavefront wavefront.launchTo run with different parameters:
roslaunch wavefront wavefront.launch goal:="-6 -2" neighbors:="8"In one terminal run:
roscd wavefront
rosrun stage_ros stageros worlds/maze.world In another terminal run:
rosrun wavefront wavefront.py x y n where x is the goal x-coordinate, y is the goal y-coordinate, and n is the number of neighbors.
The A* algorithm depends on a pre-made grid that corresponds to the configuration space of a map. This grid is a binary matrix, where 0s correspond to free space and 1s correspond to obstacles. It then computes the
By default it is assumed that the map is maze.world and its respective configuration space grid grid1.npy. If any other map is used, the user must edit Astar.py with the respective Stage parameters and configuration space grid (.npy file). If the launch file is used, the user should change its .world file.
To create configuration space grids for other maps, you can use the map_expander.py script changing the parameters as necessary and transposing the resulting map.
The robot's initial position must be set on Astar.py. When this algorithm is run with the default map the green square represents the robot and the orange square represents the goal at the default position, i.e. (5, 2).
It's possible to run the A* planner using its launch file. There is one optional argument goal, the coordinates of the goal in meters as "x_goal y_goal". The default is goal:="5 2".
To run with default parameters, simply run in terminal:
roslaunch Astar Astar.launchTo run with different parameters:
roslaunch Astar Astar.launch goal:="-6 -2"In one terminal run:
roscd Astar
rosrun stage_ros stageros worlds/maze.world In another terminal run:
rosrun Astar Astar.py x y 4where x is the goal x-coordinate and y is the goal y-coordinate.
The GVD algorithm is incomplete. It should create a Generalized Voronoi Diagram based on sensors readings.
By default it is assumed that the map is gvd.world. If the launch file is used, the user should change its .world file in order to use a different map.
It's possible to run the GVD using its launch file.
Run in terminal:
roslaunch GVD GVD.launchIn one terminal run:
roscd GVD
rosrun stage_ros stageros worlds/gvd.world In another terminal run:
rosrun GVD GVD.pyThe Coverage algorithm depends on a pre-made list that contains every Cell of the handmade Trapezoidal decomposition.
By default it is assumed that the map is trapz2.world. If the launch file is used, the user should change its .world file in order to use a different map and change the list file. The user should also change the .pickle path in coverage.py
It's possible to run the Coverage algorithm using its launch file.
Run in terminal:
roslaunch coverage coverage.launchIn one terminal run:
roscd coverage
rosrun stage_ros stageros worlds/trapz2.world In another terminal run:
rosrun coverage coverage.pyThe RRT algorithm depends on a pre-made grid that corresponds to the configuration space of a map. This grid is a binary matrix, where 0s correspond to free space and 1s correspond to obstacles. It then computes the bidirectional RRT as in Choset, Lynch, and Hutchinson1.
By default it is assumed that the map is maze.world and its respective configuration space grid grid1.npy. If any other map is used, the user must edit RRT.py with the respective Stage parameters and configuration space grid (.npy file). If the launch file is used, the user should change its .world file.
To create configuration space grids for other maps, you can use the map_expander.py script changing the parameters as necessary and transposing the resulting map.
The robot's initial position must be set on RRT.py. When this algorithm is run with the default map the green square represents the robot and the orange square represents the goal at the default position, i.e. (5, 2).
It's possible to run the RRT using its launch file. There is one optional argument goal, the coordinates of the goal in meters as "x_goal y_goal". The default is goal:="5 2".
To run with default parameters, simply run in terminal:
roslaunch RRT RRT.launchTo run with different parameters:
roslaunch RRT RRT.launch goal:="-6 -2"In one terminal run:
roscd RRT
rosrun stage_ros stageros worlds/maze.world In another terminal run:
rosrun RRT RRT.py x ywhere x is the goal x-coordinate and y is the goal y-coordinate.