Robotic Motion Planning: Cell Decompositions

[Pages:70]Robotic Motion Planning: Cell Decompositions

(with some discussion on coverage and pursuer/evader)

Robotics Institute 16-735

Howie Choset

RI 16-735 Howie Choset

Exact Cell vs. Approximate Cell

? Cell: simple region

RI 16-735 Howie Choset

Adjacency Graph

? Node correspond to a cell ? Edge connects nodes of adjacent cells

? Two cells are adjacent if they share a common boundary

c14

c4 c2

c5

c8

c7

c11

c15

c1

c

c3

10

c13

c6 c9

c12

c1

c2

c4

c5

c3

c6

c7

c8 c10

c9

RI 16-735 Howie Choset

c14 c15

c11

c13 c12

Path Planning

? Path Planning in two steps:

? Planner determines cells that contain the start and goal

? Planner searches for a path within adjacency graph

RI 16-735 Howie Choset

Types of Decompositions

? Trapezoidal Decomposition ? Morse Cell Decomposition

? Boustrophedon decomposition ? Morse decomposition definition ? Sensor-based coverage ? Examples of Morse decomposition

? Visibility-based Decomposition

RI 16-735 Howie Choset

Trapezoidal Decomposition

RI 16-735 Howie Choset

Trapezoidal Decomposition

RI 16-735 Howie Choset

Trapezoidal Decomposition

RI 16-735 Howie Choset

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download