README.md 4.67 KB
Newer Older
Edmond Irani Liu's avatar
Edmond Irani Liu committed
1
# CommonRoad Search: Search-based Motion Planner with Motion Primitives
Moritz Klischat's avatar
Moritz Klischat committed
2

Edmond Irani Liu's avatar
Edmond Irani Liu committed
3
4
5
6
7
8
9
10
This is a programming exercise for the lecture **Foundations of Artificial Intelligence** (WS20) delivered at the Department of Informatics, TUM. The task in this exercise is to implement a heuristic function and/or a search algorithm with motion
primitives to solve [CommonRoad](https://commonroad.in.tum.de/) scenarios. The following search algorithms have been implemented as examples:
	1. Breadth First Search
	2. Depth First Search
	3. Depth-limited Search
	4. Uniform Cost Search (aka Dijkstra's algorithm)
	5. Greedy Best First Search
	6. A* Search
11

Edmond Irani Liu's avatar
Edmond Irani Liu committed
12
The code is written in Python 3.7 and has been tested on Ubuntu 18.04. As the first step, clone this repository with:
13
14

```sh
Edmond Irani Liu's avatar
Edmond Irani Liu committed
15
$ git clone https://gitlab.lrz.de/tum-cps/commonroad-search.git
16
```
Edmond Irani Liu's avatar
Edmond Irani Liu committed
17
## Ways to run
18

Edmond Irani Liu's avatar
Edmond Irani Liu committed
19
You can either run the code locally, in a virtual machine, or in a docker container.
20

Edmond Irani Liu's avatar
Edmond Irani Liu committed
21
22
23
1. Ubuntu, MacOS, Windows: a [VirtualBox](https://www.virtualbox.org/) image is available in which all the necessary packages have been installed. The virtual machine image can be downloaded via `this-to-update` link. The downloading and the default login passwords are both `commonroad`.
2. Ubuntu, MacOS, Windows: a docker file and a docker image is available if you wish to run the code with docker container. Refer to `docker/README.md` for instructions. Minimum system requirements can be found [here](https://docs.docker.com/desktop/).
3. Ubuntu 18.04: If you wish to install the code locally, proceed with the installation guide below.
24

Edmond Irani Liu's avatar
Edmond Irani Liu committed
25
## Installation Guide
26

Edmond Irani Liu's avatar
Edmond Irani Liu committed
27
`skip this section if you intend to run the code in the virtual machine or in the docker container.`
Edmond Irani Liu's avatar
Edmond Irani Liu committed
28

Edmond Irani Liu's avatar
Edmond Irani Liu committed
29
We recommend using [Anaconda](https://www.anaconda.com/) to manage your environment so that even if you mess something up, you can always have a safe and clean restart. A guide for managing python environments with Anaconda can be found [here](https://conda.io/projects/conda/en/latest/user-guide/tasks/manage-environments.html).
30

Edmond Irani Liu's avatar
Edmond Irani Liu committed
31
After installing Anaconda, create a new environment with:
32
``` sh
Edmond Irani Liu's avatar
Edmond Irani Liu committed
33
$ conda create -n commonroad-py37 python=3.7
Moritz Klischat's avatar
Moritz Klischat committed
34
```
35

Edmond Irani Liu's avatar
Edmond Irani Liu committed
36
Here the name of the environment is called **commonroad-py37**. You may also change this name as you wish. In such case, don't forget to change it in the following commands as well. `Always activate` this environment before you do anything related:
37

Moritz Klischat's avatar
Moritz Klischat committed
38
```sh
Edmond Irani Liu's avatar
Edmond Irani Liu committed
39
40
41
$ conda activate commonroad-py37
or
$ source activate commonroad-py37
Moritz Klischat's avatar
Moritz Klischat committed
42
```
43
Install `Jupyter Notebook` and supplementary modules:
Moritz Klischat's avatar
Moritz Klischat committed
44
```sh
Edmond Irani Liu's avatar
Edmond Irani Liu committed
45
46
47
$ conda install jupyter ipykernel ipywidgets sphinx scipy
$ jupyter nbextension install --py widgetsnbextension --user
$ jupyter nbextension enable widgetsnbextension --user --py
Moritz Klischat's avatar
Moritz Klischat committed
48
```
Edmond Irani Liu's avatar
Edmond Irani Liu committed
49
50
51
52
53
Install `Imagemagick` (required for saving GIF animations of solutions):
```sh
$ sudo apt-get install imagemagick imagemagick-doc
```
Then, install the dependencies with:
Moritz Klischat's avatar
Moritz Klischat committed
54

Edmond Irani Liu's avatar
Edmond Irani Liu committed
55
56
57
```sh
$ pip install -r requirements.txt
```
Moritz Klischat's avatar
Moritz Klischat committed
58

Edmond Irani Liu's avatar
Edmond Irani Liu committed
59
This will install related dependencies specified in the requirements.txt. 
Moritz Klischat's avatar
Moritz Klischat committed
60

Edmond Irani Liu's avatar
Edmond Irani Liu committed
61
Next, we move on to the installation of [CommonRoad Drivability Checker](https://commonroad.in.tum.de/drivability_checker). This package provides functionalities such as collision checks, kinematic feasibility checks, road boundary checks, etc. Full installation commands are given below, other installation options can be found [here](https://commonroad.in.tum.de/docs/commonroad-drivability-checker/sphinx/installation.html).
Moritz Klischat's avatar
Moritz Klischat committed
62
63

```sh
Edmond Irani Liu's avatar
Edmond Irani Liu committed
64
65
66
$ git clone https://gitlab.lrz.de/tum-cps/commonroad-drivability-checker.git
$ cd commonroad-drivability-checker
$ bash build.sh -e /path/to/your/anaconda3/envs/commonroad-py37 -v 3.X --cgal --serializer -i -j 4
Moritz Klischat's avatar
Moritz Klischat committed
67
68
```

Edmond Irani Liu's avatar
Edmond Irani Liu committed
69
`Note`: you need to substitute `/path/to/your/anaconda3/envs/commonroad-py37` with the path to your Anaconda environment, and `X` with your python version (e. g. setting X to 7 for 3.7).
Moritz Klischat's avatar
Moritz Klischat committed
70
71


Edmond Irani Liu's avatar
Edmond Irani Liu committed
72
## Getting Started
Moritz Klischat's avatar
Moritz Klischat committed
73

Edmond Irani Liu's avatar
Edmond Irani Liu committed
74
Full description of the exercise is provided in `exercise_guide.pdf`. 
Moritz Klischat's avatar
Moritz Klischat committed
75

Edmond Irani Liu's avatar
Edmond Irani Liu committed
76
To proceed with the tutorials, open your terminal in `commonroad-search/` folder, and launch Jupyter Notebook kernel with:
77
78

```shell
Edmond Irani Liu's avatar
Edmond Irani Liu committed
79
$ jupyter notebook
Moritz Klischat's avatar
Moritz Klischat committed
80
81
```

Edmond Irani Liu's avatar
Edmond Irani Liu committed
82
In the pop-up tab (or: open http://localhost:9000/ if ran with docker, otherwise http://localhost:8888/, in the explorer), navigate to `tutorials/` and follow the tutorials.
Moritz Klischat's avatar
Moritz Klischat committed
83

Edmond Irani Liu's avatar
Edmond Irani Liu committed
84
## Implementing your search algorithm
Moritz Klischat's avatar
Moritz Klischat committed
85

Edmond Irani Liu's avatar
Edmond Irani Liu committed
86
Implement your heuristic function and/or search algorithm in `SMP/motion_planner/search_algorithms/student.py`. The usage of [PyCharm](https://www.jetbrains.com/pycharm/) is highly recommended for writing and debugging python code (freely available to students).
Moritz Klischat's avatar
Moritz Klischat committed
87

Edmond Irani Liu's avatar
Edmond Irani Liu committed
88
## Questions & Answers 
Moritz Klischat's avatar
Moritz Klischat committed
89

Edmond Irani Liu's avatar
Edmond Irani Liu committed
90
If you encountered any problem, please raise it in the [CommonRoad Forum](https://commonroad.in.tum.de/forum/) so that other students can also benefit from the answers to your questions.