9 - Global Path Planning

Question 1

Drawbacks of reinforcement learning

Answer 1

Time consuming
Trained model might end up with different routes

Question 2

Path Planning

Answer 2

Task of finding a sequence of valid configurations that will drive the robot to the goal

Question 3

Local Path Planning

Answer 3

partially known environment - take data from local sensors while moving

Question 4

Global path planning

Answer 4

Environment is static and known to robot

Question 5

Steps for djikstra algorithm

Answer 5

Assign an initial value to every node (infinite symbol often)
Repeat:
- Select an unvisited node with the smallest known distance as the current node
- Consider all its unvisited neighbours and update their distances (if applicable)
- Mark the current node as visited

Until the destination node has the smallest distance among all unvisited nodes

Question 6

Advantage of djikstra algo

Answer 6

Guaranteed to find shortest pathD

Question 7

Disadvantage of djikstra algo

Answer 7

Time consuming. Impractical for large graphs

Question 8

A* Search

Answer 8

Use a heuristic function to guide the search

F(n) = g(n)+h(n) where g(n) is distance from source to n and h(n) is an estimate to the destination from n.

If h(n) = 0 then A* equals to Djikstra’s algo

Question 9

h(n) must always ____ (under or over estimate) the cost to the goal

Answer 9

Always underestimate

Question 10

A* algorithm steps

Answer 10

Assign an initial distance (g) to every node
Initialise open and close lists (open has start; close has none)
Repeat:
- From the open list, select a node with the smallest f value as the current node (f=g+h)
- Consider all unclosed neighbours and update their value (if smaller). If its unclosed neighbours are not in the open list, add them.
- Move current node to the close list

Until destination reached.

Question 11

A* vs djikstra: Speed and memory

Answer 11

Generally faster and less memory