Home
build details

# AMOD18 The Obstavoid Algorithm

Modified 2018-12-20 by Dominik Mannhart

YouTube, The Obstavoid Algorithm

## Demo description

Modified 2018-12-19 by vklemm

This demo will show the use of a new fully-functional drive controller. It might replace the current lane follower in the future, as it is able to handle more general driving scenarios, mainly focusing on obstacles.

With the Obstavoid Algorithm, the duckiebot (now denoted as the ‘actor’) will still try to follow its own lane, exactly like the lane follower implemented by default. The advantage of the Obstavoid Algorithm is, that it takes into account every obstacle within a certain visibility range and planning horizon. The module continuously calculates an optimal trajectory to navigate along the road. If an obstacle blocks its way, the algorithm will decide on its own what maneuver will suit the best for the given situation. By predicting the motion of every obstacle and other duckiebots, the actor can, for example, be prepared for an inattentive duckie trying to cross the road, or decide if a passing maneuver is feasible with the current traffic situation, or if it should rather adjust its driving speed to wait until one of the lanes are free.

In this demo different scenarios are set up in a simulation, where you can test the Obstavoid Algorithm to its full extent.

Desktop-full installation of ROS - see here

ssh key for your computer - see here

python 2.7 - see here

pip installation - see virtualenv here

installed catkin build - see here

duckietown-world installation on local computer - see here

Docker installation on local computer - TODO, still work in progress

Fig. 1: Actor, passing a dynamic obstacle

## The Obstavoid Algorithm

Modified 2018-12-20 by Dominik Mannhart

The Obstavoid Algorithm is based on a shortest path optimization problem, which seeks the best way through a weighted, three dimensional space-time grid. The three main pillars necessary for this problem setting are the design of a suitable cost function to define the actor’s behaviour, a graph search algorithm to determine the optimal trajectory, which was implemented using the Python package NetworkX [1], and a sampler, which extracts the desired steering commands from a given trajectory and the actor’s position. In the following, each of these aspects will be further discussed and their implementation in the code architecture is briefly addressed.

Fig. 2: Example 3D cost grid illustration

## Video of expected results

Modified 2018-12-20 by Dominik Mannhart

Please add our video to the vimeo account, you can find it here: 994_AMOD18_TheObstavoidAlgorithm/movie_clips_for_vimeo/the_obstavoid_algorithm_movie.mp4

Or else watch it on YouTube here

## Duckietown setup notes

Modified 2018-12-17 by Dominik Mannhart

As this is only a demo in the simulation framework duckietown-world, no setup of a real duckietown is needed.

## Duckiebot setup notes

Modified 2018-12-17 by Dominik Mannhart

As this is only a demo in the simulation framework duckietown-world, no setup on a real duckiebot is needed.

## Pre-flight checklist

Modified 2018-12-19 by vklemm

Make sure you have a computer on which the following packages are installed (the installation has only been testes on Native Ubuntu 16.04)

• Check: Desktop-full installation of ROS - for instructions see here
• Check: that you have an ssh key for your computer here
• Check: installed pip, virtualenv here
• Check: installed catkin build here

## Demo instructions

Modified 2018-12-17 by Dominik Mannhart

## Troubleshooting

Modified 2018-12-20 by Dominik Mannhart

• 1 : Networkx library was not found: Double check that all installations were completed IN the virtual environment, especially the requirements of duckietown-world.
• 2 : duckietown-world was not found: Double check that all installations were completed IN the virtual environment, especially the setup of duckietown-world.
• 3 : The duckiebot does not see and crashes in obstacles. Have you spawned too many obstacles / actors? We have seen that too many obstacles / actors introduce a delay into the simulation which makes it impossible to avoid them in an effective manner.

## Demo failure demonstration

Modified 2018-12-19 by vklemm

Our pipeline works with a fixed field of view, which can lead to situations where it is not able to react in time to avoid an obstacle if the obstacle comes to fast from the side.

Fig. 10: Example of a failure

## Performance analysis

Modified 2018-12-19 by vklemm

To test the overall efficiency of the code, the performance of the most variable part of the code, the trajectory solver, has been measured for 100 subsequent trajectory generations. As the shortest path problem varies in computational complexity due to the obstacle configuration inside the cost grid, the solution time can vary. Nevertheless, the order of magnitude of the solution times seems not to be crucial, also if run on a Raspberry Pi.

Fig. 11: Graphical analysis of the performance

## References

Modified 2018-12-20 by Alessandro Morra

All the code can be found on github.

References:

• [1]: NetworkX documentation, a Python package for complex networks, see here [Dec. 2018]

• [2]: Dynamic Programming and Optimal Control, lecture notes by Prof. Raffaello D’Andrea, see here [Dec. 2018]

• [3]: Dijkstra’s Algorithm, Video by Compterphile, see here [Dec. 2018]

• [4]: Dijkstra’s Algorithm, Wikipedia, see here [Dec. 2018]

Further references, used in development:

• [5]: Graph algorithms, Wikipedia, see here [Dec. 2018]

• [6]: A* Algorithm, Video by Compterphile, see here [Dec. 2018]

No questions found. You can ask a question on the website.