Date: February 18, 2024

Topic: Motion Planning

Recall

Find the minimum cost path from the start to end using searching algorithms

Notes

Planning Problem

We want to find the best path given the following:

• Map
• Starting Location
• Goal Location
• Cost

Goal:

• Find minimum cost path

If all actions cost the same, then we use Breadth-First Search

Breadth-First Search

If the cost for all actions are the same, the most suitable is breadth-first search

• Since all actions (move forward, move left, move right) have the same cost, the total cost is 6

If the cost now for each action is different, we use Uniform-Cost Search

Uniform-Cost Search

In the real world, different actions have different costs

• E.g., left turns could be harder to execute due to traffic conditions

• If the cost of left turns become more expensive (20), it is more efficient to loop around with just right turns to get a total cost of 16 vs 25

• Keep track of where we have gone and the possible places to go next
• Iteratively search from the position with the lowest cost first at every time-step
• Repeat until the goal is found

Searching Algorithm (Path Planning)

• At the each position, we consider the total cost taken to get there
• Then at every step, we continuously search from the position with the lowest cost

For the diagram, where each step costs 1:

• Step 1:
  • [0, 0] - cost 0 → choose this and close for next step
• Step 2 (From [0, 0] as it has the lowest cost):
  • [1, 0] from [0, 0] - cost 1 → choose this and close for next step
  • [0, 1] from [0, 0] - cost 1
• Step 3 (From [1, 0] since both have the same cost):
  • [0, 1] from [0, 0] - cost 1 → choose this and close for next step
  • [2, 0] from [1, 0] - cost 2
  • [1, 1] from [1, 0] - cost 2
• Repeat until we reach the goal

<aside> 📌 SUMMARY: Some actions may cost more than others. We want to minimize the total cost of traveling from the start to the goal so we do an expansion algorithm that tracks a cost at every possible expansion step. At the next time step, we choose the expansion action that has the lowest cost.

</aside>

Date: February 19, 2024

Topic: A* Search

<aside> 📌 SUMMARY: A algorithm introduces an additional heuristic function that modifies the original cost. This leads to the expansion algorithm being more targeted and efficient.*

</aside>

Date: February 19, 2024

Topic: Dynamic Programming