1 of 32

ME5751�Robotics Motion Planning

Yizhe Chang chang@cpp.edu

Lecture Note Set #14

​

2 of 32

Outline

  • Voronoi Planner
  • Obstacle Avoidance or Point Tracking
    • Bug
    • Vector field histogram (VFH)
    • Curvature velocity techniques (CVM)
    • Dynamic window approach (DWA)

3 of 32

Voronoi Planner

  • Are they the same path?

Path that are homotopically the same and distinct

​

Topological constraints in search-based robot path planning, S. Bhattacharya, M. Likhachev & V. Kumar

�

4 of 32

Voronoi Planner

  • Are they the same path?

Path that are homotopically the same and distinct

(Online Generation of Homotopically Distinct Navigation Paths, Markus Kuderer et al. 2014 ICRA)

5 of 32

Voronoi Diagram

  • Voronoi diagram is a method to partition a plane into regions close to each of a given set of objects

Voronoi Diagram (Wikipedia)

6 of 32

GVD

  • Generalized Voronoi Diagram (something similar to skeleton extraction)
    • Finding pixels on a plane which has the same distance to at least 2 obstacles

​

​

https://graphics.c.u-tokyo.ac.jp/hp/en/archives/944

https://dergipark.org.tr/en/pub/cankujse/issue/49903/635661

7 of 32

Discussion: how to generate GVD on a map?

Coincidence, or intentional??

8 of 32

GVD Path Planner

  • GVD Path planner

General procedure

Start and end is treated like an “obstacle”�(Online Generation of Homotopically Distinct Navigation Paths, Markus Kuderer et al. 2014 ICRA)

​

9 of 32

GVD Path Planner

  • Homotopically distinct paths generation

​

​

Homotopically distinct path generation

�(Online Generation of Homotopically Distinct Navigation Paths, Markus Kuderer et al. 2014 ICRA)

​

10 of 32

Outline

  • Voronoi Planner
  • Obstacle Avoidance or Point Tracking

11 of 32

Path Planner vs Obstacle Avoidance

  • Path planning:
    • Planning a trajectory on a known map
    • Usually do not consider the kinematics or dynamics constraints of the robot
  • Obstacle Avoidance:
    • Rely on real-time sensor reading: an obstacle may not show up in the map but is detected by the sensor
    • Usually consider the kinematics constraints of the robot
    • The goal configuration and start configuration is usually not far
    • Can be used for point tracking

​

12 of 32

Bug (“Bug 0”) Algorithm

start

goal

13 of 32

Bug Algorithm

  • From start to the goal

14 of 32

Bug 0 Algorithm

  • Chance driven

15 of 32

Bug 1 Algorithm

  • If we add some

16 of 32

Bug 1 Algorithm

17 of 32

Bug 1 Algorithm Pseudo code

18 of 32

Bug 2 Algorithm

19 of 32

Bug 2 Algorithm

  • If you are unlucky…

20 of 32

Bug 2 Algorithm

21 of 32

Bug Algorithm

  • Deal with unknown obstacles
  • Easy to implement
  • Easy to cooperate with simple range sensors (IR, sonar, etc…)

​

  • Low efficient, your car move slowly to follow the obstacle contour
  • Rely on current sensor reading, treat the computer as an idiot

22 of 32

Outline

  • Voronoi Planner
  • Obstacle Avoidance or Point Tracking
    • Bug
    • Vector field histogram (VFH)(Figures from: Borenstein, Johann, and Yoram Koren. "The vector field histogram-fast obstacle avoidance for mobile robots." IEEE transactions on robotics and automation 7, no. 3 (1991): 278-288.)
    • Curvature velocity techniques (CVM)
    • Dynamic window approach (DWA)

23 of 32

Vector Field Histogram (VFH)

  • We can build a “local obstacle probability map”

​

24 of 32

Vector Field Histogram

25 of 32

Vector Field Histogram

  •  

26 of 32

Vector Field Histogram

  • Suitable for inaccurate, small area of view range sensors (sonar, e.g.)
  • Need to cooperate with wheel odometer to generate a “360 deg” histogram
  • Further development to VFH+, VFH*

​

  • Now, the 360 deg LIDAR is, pretty cheap

27 of 32

Outline

  • Voronoi Planner
  • Obstacle Avoidance or Point Tracking
    • Bug
    • Vector field histogram (VFH)
    • Curvature velocity techniques (CVM) (Simmons, Reid. "The curvature-velocity method for local obstacle avoidance." In Proceedings of IEEE international conference on robotics and automation, vol. 4, pp. 3375-3382. IEEE, 1996.)
    • Dynamic window approach (DWA)

28 of 32

Curvature Velocity Method

  • Curvature Velocity Method (CVM) fully considers the robot’s kinematics and dynamics constraint

29 of 32

Curvature Velocity Method

  • Configuration space:
  • rotational velocity (rv) and translational velocity (tv)
  • Objective function is to be maximized:

​

30 of 32

CVM result

  • The trajectory by “fixing the tv”

31 of 32

Outline

  • Voronoi Planner
  • Obstacle Avoidance or Point Tracking
    • Bug
    • Vector field histogram (VFH)
    • Curvature velocity techniques (CVM) (Simmons, Reid. "The curvature-velocity method for local obstacle avoidance." In Proceedings of IEEE international conference on robotics and automation, vol. 4, pp. 3375-3382. IEEE, 1996.)
    • Dynamic window approach (DWA)

32 of 32

Dynamic Window Approach

  • An ultimate search-based method that considers the robot dynamic constraint
  • We will discuss it later
  • http://wiki.ros.org/dwa_local_planner

​