Robot Path Planning

Download as pdf or txt
Download as pdf or txt
You are on page 1of 29

Robot Path Planning

2 of 25 29

A* Search

! Imagine we have a robot that lives in a 2D grid. ! The robot is provided with:
!an occupancy grid map of the world !the current robot position !and a goal position

! The robot needs to plan a path from the current position to the goal position.

3 of 25 29

Path Planning
How do I get from my current location S to my goal location G?

4 of 25 29

Contents
How do I get to my goal?

Today we will look:


!Dijkstras Algorithm and A* Search to Find the Shortest Path !Dynamic Programming to Find the Best Policy

5 of 25 29

DIJKSTRAS ALGORITHM

6 of 25 29

Dijkstras Algorithm

! Dijkstras Algorithm works by visiting locations in the map starting with the ones closest to the start position. ! One it has visited a location it then goes to the location closest to the start point that has not yet been visited. ! So it expands outwards from the start point until it reaches the goal.

7 of 25 29

Dijkstras Algorithm

! Distance Update: ! Assign each location an estimated distance from the starting position: start=0, else=infinity ! For each cell: if the distance from the cell to the starting point + the distance from the cell to its neighbour is less than the neighbours current estimated distance update the neighbours distance estimate and remember which cell you updated it from. ! Mark a cell as visited once you have checked all its neighbours distances.

8 of 25 29

Dijkstras Algorithm

9 of 25 29

Dijkstras Algorithm

10 of 25 29

Dijkstras Algorithm

11 of 25 29

Dijkstras Algorithm

Notice that all the cell are now on the closed list: i.e., we have updated the distances of all the cells even the cells that we probably wont visit, such as those on the top row

12 of 25 29

Dijkstras Algorithm

! Find Shortest Path ! Once the goal has been visited you can generate the shortest path by working back from the goal along the path of cells that updated their neighbour last.

13 of 25 29

Dijkstras Algorithm

14 of 25 29

A* Search

15 of 25 29

A* Search

! Dijkstras Algorithm did generate the shortest path for us. ! But it does so by updating the distances for every location on the map (potentially multiple times). ! A* search allows us to generate a shortest path without doing this repetitive updating.

16 of 25 29

A* Search

! A* search uses a heuristic function to estimate the distance from a cell to the goal. ! It then expands the cell on the open list with the smallest f value where the f value is the cost of reaching the cell from the start state plus the heuristic estimate of the distance from that cell to the goal.

17 of 25 29

A* Search

18 of 25 29

A* Search

Notice that the cell on the top row are still on the open list.

19 of 25 29

A* Search

! We can then reconstruct the shortest path as follows:

! This will give us back the same path as Dijkstras algorithm but we have not had to expand as many nodes.

20 of 25 29

DYNAMIC PROGRAMMING FOR ROBOT PATH PLANNING

21 of 25 29

Dynamic Programming

In dynamic programming we break up a problem into a series of overlapping subproblems and build up solutions to larger and larger subproblems. Each time we solve a subproblem we store the solution and reuse it when we are solving a larger problem. DP has many applications but today we will apply it to robot path planning.

22 of 25 29

POLICY

Unlike Dijkstras algorithm and A* Dynamic Programming for Robot Path Planning returns the shortest path from anywhere in the map. This is useful in stochasitc worlds because we may get knocked off our planned path due to the nondeterminacy of actions.

23 of 25 29

POLICY

The result of applying DP to path planning is that each cell in the map is labeled with the optimal action that should be taken at that location to reach the goal.

24 of 25 29

POLICY

The mapping from a cell location to an action is called a Policy i.e., it determines what we should do at each location.

25 of 25 29

Value Function

! The first step in computing the Policy is to compute the value function for the map. ! For each grid cell in the map the value function returns the length of the shortest path to the goal. ! The value function can be computed by recursively working back from the goal and taking the distance from the optimal neighbour of a cell and adding the cost of getting to that neighbour.

26 of 25 29

Value Function

The DP element of the algorithm is that we compute the value for a cell store this in memory and then use this value to compute the value of the next cell.

27 of 25 29

Value Function and Policy

The translation from value function to policy is done using hillclimbing, you simply take the action that moves you to the neighbour with the minimum value. Given a policy the robot knows what action to take no matter where it ends up on the map it is ready for all contingencies.

28 of 25 29

Robot Path Planning

29 of 25 29

Questions

You might also like