MPDM 4 (Global Planning)

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/7

encourage image

There's no tags or description

Looks like no tags are added yet.

8 Terms

1
New cards

Workspace W and Configuration Space C

Picture

<p>Picture</p>
2
New cards

Inputs & Outputs

1. User Information
(Destination, Requirements)

2. Localization
(Global Navigation Satellite System (GNSS), LiDAR-/Camera Localization, State: [𝒙, 𝒚, 𝒛, 𝒗, 𝜽])

3. Map
(2D (grid map, camera-based map), 3D (terrain map, LiDAR-based map))

4. Result: Global Plan from A to B

3
New cards

Objective

(1) Find a route from start to destination

(2) Route has to be feasible

(3) Route has to be effective

(4) Route has to be efficient

4
New cards

Discrete vs. Continuous Planning

Discrete states
Environment devided in states: grids or graphs
Advantage: A* can find the graph optimum
Disadvantage: Coarse grids can miss better paths
Map → Discretization → Planning
(Dijkstra‘s Algorithm, A*-Algorithm)

Continuous states
Planning in continuous space
Advantage: Flexible paths without a fixed grid
Disadvantage: No automatic smoothness or optimality

<p><strong>Discrete states</strong><br>Environment devided in states: grids or graphs <br><u>Advantage:</u> A* can find the graph optimum<br><u>Disadvantage:</u> Coarse grids can miss better paths<br>Map → Discretization → Planning<br>(Dijkstra‘s Algorithm, A*-Algorithm)</p><p><strong>Continuous states</strong><br>Planning in continuous space<br><u>Advantage:</u> Flexible paths without a fixed grid<br><u>Disadvantage:</u> No automatic smoothness or optimality</p>
5
New cards

Graph-based Planning. Basic elements

Picture

<p>Picture</p>
6
New cards

A*-Algorithm

Extends Dijkstra's algorithm with a heuristic that directs the search toward the goal.

Complete; optimal if h(n) never overestimates the true cost (admissible)

Informed Heuristic Search Algorithm: A* uses a heuristic to guide its search, making it more directed towards the goal

Differences to Dijkstra’s algorithm:
- Informed Heuristic Search Algorithm: A* uses a heuristic to guide its search, making it more directed towards the goal.
- Estimation Function to Accelerate Search: The heuristic function estimates the cost from the current node to the destination, enabling A* to prioritize paths that are more likely to reach the target efficiently.
- Node Cost Calculation: A* evaluates the cost of each node as the sum of the distance from the start node to the current node (actual cost) and the estimated distance from the current node to the goal (heuristic cost). The node with the lowest combined cost is prioritized for exploration.

<p>Extends Dijkstra's algorithm with a heuristic that directs the search toward the goal.</p><p>Complete; optimal if h(n) never overestimates the true cost (admissible)</p><p>Informed Heuristic Search Algorithm: A* uses a heuristic to guide its search, making it more directed towards the goal</p><p><u>Differences to Dijkstra’s algorithm:</u><br>- Informed Heuristic Search Algorithm: A* uses a heuristic to guide its search, making it more directed towards the goal.<br>- Estimation Function to Accelerate Search: The heuristic function estimates the cost from the current node to the destination, enabling A* to prioritize paths that are more likely to reach the target efficiently.<br>- Node Cost Calculation: A* evaluates the cost of each node as the sum of the distance from the start node to the current node (actual cost) and the estimated distance from the current node to the goal (heuristic cost). The node with the lowest combined cost is prioritized for exploration.</p>
7
New cards

Global Trajectory: Optimization

Path Planning (Geometric QP) + Velocity Planning

Possible objectives:
(1) Shortest distance: We travel the shortest distance
(2) Minimum curvature: We reduce the steering of the wheel

+ Picture

<p>Path Planning (Geometric QP) + Velocity Planning</p><p>Possible objectives:<br>(1) Shortest distance: We travel the shortest distance<br>(2) Minimum curvature: We reduce the steering of the wheel</p><p>+ Picture</p>
8
New cards

General comment

Hard to make flashcard from this lecture
Mb just study the slides?