ME5751 - Module 2

ME5751

Module 2:

Brushfire Algorithm

Learning objective:

1. Implement Brushfire algorithm

2. Understand how potential field map is generated

Equipment:

1. A personal computer

Mission statement

Given an occupancy grid, get the potential map (with inflation) for the occupancy grid using brushfire algorithm

Writing and submission:

1. Submit a working package on Canvas Alternatively, you may set up your own Github or bitbucket page. Put the page link in your lab report, see below)

2. Write a lab report and submit it on Canvas in IEEE conference proceeding format or ASME conference proceeding format: (2-8 pages).

Include an abstract to describe what you have achieved
Survey on grid-based map representation and grid-based planning methods
Briefly discuss the procedure of Brushfire algorithm, describe how you initialize the queue, and how you define "distance" to obstacles at 4-connection or 8-connection. (There will be a bonus if you use 8-connection with your own idea!)
Make your own occupancy grid map. You need to self-create 3 maps (with your own narrative of why these maps are worth testing). All the maps shall have 500 x 500 pixels. Report all maps in the experiment section.
You must generate the "distance map" (i.e. the cell value is the distance to the nearest obstacle). From the distance map, you can generate the cost map (potential map) with inflation. The way to define potential function is of your choice. Report how you generate the "distance map", and what is your potential function. You can use different potential functions and discuss the pros and cons of each.

Grading

Lab reports and programming should be done in pair of 2 or individually. Between groups you are allowed to collectively interpret material and understand the course package; sharing code or lab reports will be considered a violation of course policy.

1. 50%: functional code with adequate annotation

2. 15%: well-organized abstract, introduction, and method description

3. 35%: Experiment result report, analysis, and discussion

5. 10% bonus max at the discretion of the instructor: any better way to generate the cost map? Any better way to process a 8-connection map?

Part 1: Download the updated map

1. Install missing dependencies. You may need to install OpenCV: on Windows: pip install opencv-python; On Linux: sudo pip install opencv-python

2. If you cannot install OpenCV, follow OpenCV-python page to check further dependencies. Make sure to follow the instruction strictly: you can only install one version of OpenCV.

Part 2: Browse the course dialogue window

1. Run E160_gui.py

(If you use python IDLE, simply File->open->E160_gui.py; then click run (F5))

(If you use Command Prompt/Terminal, navigate to the directory you extracted your course package (Windows, Linux), (mostly you will use `cd Folder_Name`), type `python E160_gui.py` or `py E160_gui.py`).

2. You should be able to see the dialogue with a map in the background as in Fig 1. Click "toggle map", and you will see a strange "potential map" as in Fig 2. (It looks strange now because it is your task!)

3. See below if your canvas is too big, or you cannot see the map.

Part 3: Browse "cost_map.py"

1. This is the file you will modify to achieve the Brushfire algorithm. Your effort is modifying compute_costmap(self) method at line 74.

We have some parameters set in the __init__(self) method.

We define 1 pixel as 1cm (0.01m);
We set the Canvas size to be 500 x 500, you can adjust the size of Canvas in E160_graphics line 18 :

self.scale = 250 #This number should be the same as the map size divided by 2

For debugging purposes, you can choose a smaller map and select the self.scale above to be smaller.
The inflation radius is the radius of the robot. Let's set it as 18 now, although we know the robot radius is 12.
The original occupancy grid is `testmap.png` in the map folder; if your map doesn't show properly, check if `testmap.png` is there;
self.save_vis_map() will save a "visualization map" to visualize your costmap.
self.save_costmap() will save a .txt file of your costmap.

2. If map loading is successful, the map is saved in a 2d numpy array `self.map`; another 2d numpy array `self.costmap` is initialized by copying `self.map`.

self.costmap has the same dimension as self.map;
the map_width and map_height is 2 x self.graphics.scale; they are equal at this time;
update on self.costmap will not change self.map, vice versa;
The self.vis_map is the map you will visualize. It is generated at get_vis_map method. You may update this method for a better rendering of your cost map.

Part 4: Prepare occupancy grid

1. Occupancy grid is a gray-scale png file; you can generate it using most of painting tools (MS Paint, Pinta)

2. the pixel number of the png file is advised to be the same as the pixel number you specified in `cost_map.py`. In your submission

3. all colors will be converted to grayscale; therefore, it is recommended to use only black and white for the occupancy grid;

Part 5: Make your cost map

All your efforts should be put in `self.compute_costmap(self)` method. Feel free to define more methods or classes to help you complete your task. Here are a few hints and reminders:

1. Pixel value: white is 255, and black is 0 for the loaded self.map

2. You are recommended to get the "distance map" to get the distance to the nearest obstacle for each free pixel; then, inflate the map based on self.radius; then, assign a cost to each distance.

3. self.costmap is a 2d NumPy array. It is basically the same as any 2d array in any computer language. Click here for a lengthy tutorial. ChatGPT usually does an excellent job in generating demonstrations on 2d array operation.

Figure 1. An occupancy grid you must replace

Figure 2. A wrong potential map

Google Sites

Report abuse