ME5751 - Module 4

ME5751

Module 4:

Probabilistic road map

Learning objective:

1. Implement single query PRM

2. Explore methods to optimize path generated by single query PRM

Equipment:

1. A personal computer

Mission statement

Given an occupancy grid with cost map, a goal position, can you plan a path between your current position to goal position?

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).

Grading

Lab report ad programming should be done in pairs of 2. 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

You should try your algorithm on 3 different maps (hopefully different styles) you made. Make sure you inflated the map!
Discuss how many nodes you randomly expanded to reach the goal
If possible, vary the way you random a new configuration c'. You can add limitations on possible configuration c' and discuss the limitation.
Any way to integrate the cost map?
Any way to integrate the wheel kinematics, so the path between two configurations is not a straight line and can be directly executed by the robot? (Huge bonus on this!)

5. 10% bonus max at the discretion of the instructor: do something cool?

Part 0: An example of Prompt

The topological structure can be completed by generative AI. Check this prompt result.

Part 1: Download new package

1.There may be updates, do NOT replace your previous package

2. Install missing dependencies using Pip

Part 2: Browse "prm_planning.py" and do PRM!

1. We defined three classes for you: prm_node, prm_edge, and prm_tree; you may select to use them, or you can define your own.

2. Your major code should be in def plan_path(self) function, feel free to use additional function to support your programming

3. We provide bresenham(x1, y1, x2, y2) algorithm for you. Bresenham algorithm helps you find all coordinates on the straight line path between (x1, y1) and (x2, y2). If any of the coordinates belong to an obstacle pixel, the configuration between (x1, y1) and (x2, y2) cannot be connected.

4. Like last time, to get the potential map (aka costmap) you acquired in your cost_map.py, you can simply self.costmap.costmap

5. You must optimize your path if you use single query PRM as described in our slides. Implement non-optimized first, see what you can get, and think of a method for optimization to remove all loops in the path.

Supplement: How to switch between A* and PRM planner?

We have 2 global planners! You can decide which to use for final. Or you can use a third one.

Simply navigate to `E160_graphics.py`

If you want to switch back to A*, leave `from path_planner import *` and comment out `from prm_planner import *`

Fig 1. Red path reflect the path we planned. In this case, it is wrong.

Google Sites

Report abuse