README.md 5.88 KB
Newer Older
1
2
# Graph Search-Based Motion Planner with Motion Primitives

3
This is a programming exercise for the lecture **Introduction to Artificial Intelligence** and **Gems of Informatics II** delivered at the  Department of Informatics, TUM. Please clone this repository or download it using the button at the upper-right corner. The repository has the following folder structure:
4
5
6
7
8
``` code-block:: text
commonroad-search/
	├GSMP/
		├motion_automata/
			├automata/
9
			├figures/
10
11
12
13
			├motion_primitives/
			└vehicle_model/
		└tools/
			├commonroad-collision-checker/
14
15
16
			├commonroad-road-boundary/
			├docker/
			└motion_primitives_generator/
17
18
19
	├notebooks/	
		├batch_processing/
		└tutorials/
20
	├pdfs/	
21
	├scenarios/
Edmond Irani Liu's avatar
Edmond Irani Liu committed
22
23
		├exercise/
		└tutorial/
24
25
	└solutions/ 
```
26
The codes are written in Python 3.7 and tested on Ubuntu 18.04. 
Moritz Klischat's avatar
Moritz Klischat committed
27

28
## Ways to Install
Moritz Klischat's avatar
Moritz Klischat committed
29

30
31
You can either install the softwares on your own machine, use a virtual machine image or run a docker image.

32
1. Own machine (Works on Ubuntu): Please follow the installation guide below if you are using your own machine. 
Moritz Klischat's avatar
Moritz Klischat committed
33
2. Virtual machine (`Recommended` for Ubuntu, Mac OS & Windows): Alternatively, you can use the virtual machine image provide by us, in which all the necessary modules are installed already. You can down the virtual machine image via [this](https://syncandshare.lrz.de/getlink/fiBX3hqrmDo5DKpGysFGNDie/07_VirtualMachine) link and run it in Virtual Box. The downloading password and default login password are both `commonroad`. 
34
3. Docker (Works on Ubuntu, Mac OS with OS X El Capitan 10.11 or later, Windows 10 64-bit: Pro, Enterprise, or Education, Build 15063 or later): Also, you can run a docker image provided by Tom Dörr. After installing docker, you can run the image using command
35
36
37
38
39

```sh
docker run -it -p 9000:8888 --mount src="$(pwd)",target=/commonroad-search,type=bind tomdoerr/commonroad-search
```

40
     and open the Jupyter Notebook by visiting `localhost:9000` in your web browser.
41

42
After you have set up your environment, please further proceed with `pdfs/0_Guide_for_Exercise.pdf`. 
43
44
45
46

## Installation guide

`Skip this section if you intend to use the provided virtual machine or docker image.`
Edmond Irani Liu's avatar
Edmond Irani Liu committed
47

48
49
50
51
52
We recommend using [Anaconda](https://www.anaconda.com/) to manage your environment so that even if you mess up something, you can always have a safe and clean restart. A guide for managing the environments can be found [here](https://conda.io/projects/conda/en/latest/user-guide/tasks/manage-environments.html). Also, the usage of [PyCharm](https://www.jetbrains.com/pycharm/) is highly recommended (free version available for students).

After installing Anaconda, create a new environment by command:
``` sh
 $ conda create -n commonroad-py37 python=3.7
Moritz Klischat's avatar
Moritz Klischat committed
53
```
54
55
56
57
58

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:

Moritz Klischat's avatar
Moritz Klischat committed
59
```sh
60
61
  $ conda activate commonroad-py37
  or
Moritz Klischat's avatar
Moritz Klischat committed
62
63
  $ source activate commonroad-py37
```
64
Install `Jupyter Notebook` and supplementary modules:
Moritz Klischat's avatar
Moritz Klischat committed
65
```sh
66
  $ conda install jupyter
Moritz Klischat's avatar
Moritz Klischat committed
67
  $ conda install ipykernel
68
  $ pip install ipython-autotime
69
  $ pip install PyYAML
Moritz Klischat's avatar
Moritz Klischat committed
70
71
  $ conda install ipywidgets
  $ conda install sphinx
Edmond Irani Liu's avatar
Edmond Irani Liu committed
72
  $ conda install scipy
73
74
  $ jupyter nbextension install --py widgetsnbextension --user
  $ jupyter nbextension enable widgetsnbextension --user --py
Moritz Klischat's avatar
Moritz Klischat committed
75
76
```

77
This exercise has three main dependencies that need to be installed.
Moritz Klischat's avatar
Moritz Klischat committed
78

79
### 1. CommonRoad-io
Moritz Klischat's avatar
Moritz Klischat committed
80

81
As documented in CommonRoad-io [Documentation](https://commonroad.in.tum.de/static/docs/commonroad-io/index.html), type in the following command to install the package:
Moritz Klischat's avatar
Moritz Klischat committed
82
83

```sh
84
  $ pip install commonroad-io
Moritz Klischat's avatar
Moritz Klischat committed
85
86
87
88
```


### 2. CommonRoad-Collision-Checker
89
Go to folder `GSMP/tools/commonroad-collision-checker/` and follow the instruction in README.rst. (You may navigate to it from this page for a better rendering of the .rst file)
Moritz Klischat's avatar
Moritz Klischat committed
90

91
A tutorial of CommonRoad Collision Checker can be found [here](https://commonroad.in.tum.de/tutorials/).
Moritz Klischat's avatar
Moritz Klischat committed
92

93
### 3. CommonRoad-Road-Boundary
94
Go to folder `GSMP/tools/commonroad-road-boundary/` and follow the instruction in README.md. (You may navigate to it from this page for a better rendering of the .md file) In case you face an error, refer to troubleshooting section. 
Moritz Klischat's avatar
Moritz Klischat committed
95

96
97
98
99
## Tutorials

Navigate your terminal to `commonroad-search/` folder, and start Jupyter Notebook with:
```shell
Moritz Klischat's avatar
Moritz Klischat committed
100
101
102
  $ jupyter notebook
```

103
In the prompt up page, navigate to `notebooks/tutorials/` and follow the tutorials `tutorial_commonroad-search.ipynb`, `cr_uninformed_search_tutorial.ipynb`, and `cr_informed_search_tutorial.ipynb`.  Remember to refer to `pdfs/0_Guide_for_Exercise.pdf` for additional explanation. The executed Jupyter notebooks for tutorials can also be found [here](https://commonroad.in.tum.de/tutorials/).
Moritz Klischat's avatar
Moritz Klischat committed
104
105
106

## Implement your own search algorithm

107
Open `GSMP/motion_automata/automata/MotionPlanner.py`. Write your own heuristic functions and/or search algorithm in the following functions:
Moritz Klischat's avatar
Moritz Klischat committed
108
109

```python
110
111
	def calc_heuristic_cost()
	def search_alg()
Moritz Klischat's avatar
Moritz Klischat committed
112
113
```

114
There are already two search algorithms, namely `A*` and `Greedy Best First Search`, implemented as examples for you. You are free to refer to them for some inspiration.
115
The `A*` is not working perfecly and should only serve as code reference how a heuristic can be developed.
Moritz Klischat's avatar
Moritz Klischat committed
116

117
## Troubleshooting
Moritz Klischat's avatar
Moritz Klischat committed
118

119
### 1. Boundary library not working properly
Moritz Klischat's avatar
Moritz Klischat committed
120

121
122
If there are errors stating not finding the boundary library (e. g. module `construction` not found) while going through the second tutorial, try manually copying all the contents under folder `GSMP/tools/commonroad-road-boundary/`  into `/path/to/your/anaconda3/envs/lib/python3.7/site-packages/commonroad-road-boundary/`. 
`Make sure to copy all files within the folder manually, not just copying the folder it self. Also, remember to add this path to your IDE's (e. g. PyCharm) interpretor path.`