CURSO DE PATH PLANNING

Página 1

CH1: Sensor Based Planning

Problem: Move from point A to point B

solution: teh problema depends on robot´s sensor and capabilities

Assumptions: (workspace)

- a workspace W is a subset of R en 2 d

- finite # of obstacles O1, O2, O3 ... On

- a star point Pstart and end point Pgoal, in the freworkspace

DEFINITION: Free workspace Wfree:= W\(O1 U O2 U... U On)

Assumptions: (robot)

- robot is describe by a moving Paint (no size)

- knows directions towards goal E distance

- knows nothing abouts the obstacles

- has a contact sensor to locally detect obstacles

- can move in a straigh line toward goal follow the boundwy of an obstacle

1.2 The bug 0 algorithm

___________________________________________________________________________

Bugs 0 Algorithm

1: while not at goal

2: move towards goal

3: if hit an obstacle

4: while not able to move towards goal

5: follow obstacle boundary moving to the left

______________________________________________________________________

This algorithm doesn´t always find the goal.

1.3 The bug 1 Algorithm

- it´s not surprising that Bug 0 doesn´t always find a path

the algorithm isn´t using all of the robots capabilities

- Doesn´t use distance

- Doesn´t use memory

Bug 1 Algorithm

_______________________________________________________________

1: while not al goal

2: move towards goal

3: if hit an obstacle

4: circunnavigate if ( left or right) while circunnavigation

store in memory distance from boundary to goal

5: follow boundary back to point w min distance to goal

______________________________________________________________

Página 2

1.3.1 Implementation details

- Simplest implementation

- when a robot hit s obstacle,save distance & direction

- us robot circunnavigates , it stores the mínimum

distance to the goal

- Cirunnavitagion is complete when distance & direction matches stored values

- partially cirnunnavigate obstacle again until distance equals the min saved in memory

more sophisticated versión:

- If robot can measure travelled distance while circunnavigating then it can return to the min distance path using the shorest path

-

Página 3

1.3.3 Performance of Bug I Algorithm

- rigorous analysis there are two desirable properties

*optimality ( w/ respect to some metric) , and

* completeness (i.e correctness an appropriate sense)

- what is the lenght of path generate by Bug 1? Hard to answer. Easier questions

ii) will Bug 1 find the shortest path?

iii) Can we find upper and lower limits on path length?

iv) are there enviroments in wich the upper bound is achieved?

Notations: D:= length of line from Pstart to Pgoal

perimeter (O;) := length of perimeter of obstacle i

Theorem: ( Performance of Bug 1) Consider a workspace W/ n obstacles and asume Bugs 1 find a path to goal. Assuming the robot doesn´t have a linear odometer the following is true:

i) General. Bug1 doesn´t find the shorest path

ii) Path length is lower by D

iii) path length is upper bounded by D+2Sum from i =1 to n perimeter (O;)

iv) there are enviroments where upper bound is achieved.

Remark: if the robot has a linear odometer the upper limit is

D+ 3/2 Sum(i=1 to n) perímetro(Oi)

Página 4

1.4 Bug 2 Algorithm

DEFN: The start-goal line is the unique line between Pstart & Pgoal

Bug 2 prelim algorithm

_______________________________________________________________________________________________

1: while not at goal

2: move towards goal along star-goal line

3: if hit an obstacle

4: follow boundary until you hit stargoal línea again and are able to move towards goal

________________________________________________________________________________________________

- when te leave an obstacle we´alwaysc closer them where we hint

- when a moving along can obstacle an inscreas but after the search phase the robot is closer

- thus the distance to the goal is a monotonically drecresing function ot he off of obstacles

Página 5

Summary: Bug 1 performs exhaustive search by examining all posible leave points before coomithing to the optimal choice. Bug2 is a greedy algorithm and takes the first available leave point closer to goal

Robot Capabilities Bug 0 Bug 1 Bug 2

Direction goals yes yes yes

Distance to goal no yes yes

memory no yes yes

linear odometer no optional no

angular odometer no yes yes

the angular odometer is needed for direction to goal. It is needed in Bug I to figure out when circumnavigation is complete and in Bug 2 to determine when start-goal line is hit

the direction to goal must be stored in a known reference frame (i.e counter clockwise angle relativeto a fixed x-axis

a compass gives an angle with respect to a fixed orientation

an angular odometer measure changes in heading,

robots uses initial heading at Pstart as te orientation or reference frame

the directions to goal is given as alfa2+alfa3

alfa2 is measured w/odometer

alfa3 is the output of the "direction to goal sensor"

excersise six, seven,

Página 6

CHAPTER 2 Motion planning via descomposition and search

i study techniques for descompositiong a workspace into convex regions

ii Define roadmaps when encode the descomposed workspace

iii introduce graph algorithms for computing point-to-point paths

2.1 Problem formulation and assumptions

- workspace W in space R2; some obstacles O1 O2 ...On: a Start point and Goal point

a robot described by a moving point (no área/no volumen)

Wfree:= W\(O, U O2,U O3 ... U On)

Assumption (robot) The robot knows Pstart, Pgoal, W, and O1, O2, O3 ... On

Assumption (enviroment) i) workspace is a bounded polygon

ii) finite# of obstacle also polygons

iii) Pstar/Pgoal is Wfree

Comparation to CH1

Similaraties: robot is a point, robot can move in any direction

Differences: robot has no sensors but i know Wfree

- were interested in obtaining a sequence of pre-computed steps where as before sensor bases algorithms deal W/ obstacles along the way

2.1.1 Polygons

- for us polygon is a figure composed of a finite number of line segments (sides or edges) closing in a loop.

- we number the vértices in a counterclockwise order

-

2.2. Workspace descomposition

Defintion: A set S is convex if for any x, y eS the line segment connecting them is entirely in S

eg convex and no convex

Polygons in R2 are convex is and only if all its interior angles are < pi (180°)

Planning in non-convex sets using convex descompositions

- is Pstart and Pgoal are in the same convex, obstacle free set then the line segment connecting them is collision free

- if Wfre is not convex the following pciture suggest an algorithm for getting paths

Página 7

2.3 Search Algorithms over graphs

In the last algorithm we didn´t specify what type of object a roadmap is nor search it

in short a roadmap is (i) a graph and (2) path is a roadmap one found using graph search algorithms

Defn: A graph G is a pair (V,E) consisting of a finite set of vértices V={1,2,3,... ,n}and a set of edges E correspondientes VxV

if {i,j} is an edge, we say that vertex i and vestox jare neighbors

BASIC TERMS:

i) a path is ordered sequence of vértices such that from each vertex there is on edge to the next vertex is the sequence

[the length or a path, is the number of edges from start to end]

ii) Two nodes are path connected if these exists a path between them. A graph is connected if any two novede are connected

iii) the shoretest path between tew

The roadmap generated by the wok is the dual grapch

problema: mm

- the breadth seach algortim

The breadht fits..