What is it? Methods that explore C-space by randomly sampling configurations and connecting them.
RRT: Grow tree from start toward random samples. RRT*: Optimal variant with rewiring. PRM: Build roadmap by sampling + connecting neighbors.
Sampling-Based Planning
What is it? Methods that explore C-space by randomly sampling configurations and connecting them, avoiding explicit construction of C-space obstacles.
RRT Rapidly-exploring Random Tree
Idea: Grow a tree from start toward random samples, biased toward unexplored regions.
- Sample random point qrand
- Find nearest node qnear in tree
- Steer from qnear toward qrand by step size ε
- If collision-free, add new node to tree
✏️ Sketch: Draw tree branching out from start, with random samples pulling it toward unexplored space.
RRT* Optimal RRT
Key difference: Asymptotically optimal - finds shortest path as samples → ∞.
- Find neighbors within radius r (not just nearest)
- Choose best parent - connect to neighbor giving lowest cost-to-come
- Rewire - check if new node is better parent for neighbors
r = γ·(log(n)/n)^(1/d)
✏️ Sketch: Show rewiring - dashed line to old parent, solid to new better parent.
RRG Rapidly-exploring Random Graph
Idea: Like RRT* but creates a graph instead of tree.
- Connect new node to ALL collision-free neighbors in radius
- Multiple paths to each node (redundancy)
- Useful when you need alternative routes
✏️ Sketch: Show node with multiple edges to neighbors, not just one parent.
PRM Probabilistic Roadmap
Idea: Two-phase approach for multi-query planning.
- Learning phase: Sample N random configs, connect neighbors within radius r if collision-free → build roadmap graph
- Query phase: Connect start/goal to roadmap, run Dijkstra/A*
✏️ Sketch: Scattered nodes connected by edges forming a network. Start/goal connect to nearby nodes.
Comparison
| Method | Optimal? | Multi-query? |
|---|---|---|
| RRT | No | No |
| RRT* | Yes (asymp.) | No |
| RRG | Yes (asymp.) | Partial |
| PRM | Roadmap-optimal | Yes |
RRT Family
PRM
Topic Guide
RRT Steps
RRT
1. Sample Random Point
2. Find Nearest Node
3. Steer / Extend
4. Check Collision
5a. Find Neighbors (RRT*)
5b. Add to Tree
6. Rewire Neighbors (RRT*)
7. Success!
PRM Steps
Multi-Query
1. Sample N Nodes
2. Connect Neighbors (k-NN)
3. Connect Start & Goal
4. Graph Search (A*)
5. Path Found!
Multi-Query Advantage:
Once roadmap is built, it can be reused for multiple start/goal queries without rebuilding!
Exam Questions & Answers
1. What is the main idea of sampling-based motion planning?
Instead of explicitly computing Cfree, we sample random configurations and check collision.
Build a graph/tree in C-space incrementally. Avoids curse of dimensionality.
"Náhodné vzorkování konfiguračního prostoru místo explicitního výpočtu."
"Náhodné vzorkování konfiguračního prostoru místo explicitního výpočtu."
2. Multi-query vs Single-query algorithms?
Multi-query (PRM): Preprocessing phase builds roadmap. Reusable for multiple queries.
Single-query (RRT): Builds tree from scratch for each query. Better when environment changes.
"PRM = předzpracování, RRT = od nuly pro každý dotaz."
Single-query (RRT): Builds tree from scratch for each query. Better when environment changes.
"PRM = předzpracování, RRT = od nuly pro každý dotaz."
3. What is Probabilistic Completeness?
If a solution exists, the probability of finding it approaches 1 as the number of samples → ∞.
"Pravděpodobnost nalezení cesty jde k 1."
P(find path | path exists) → 1 as n → ∞
"Pravděpodobnost nalezení cesty jde k 1."
4. What is Asymptotic Optimality?
The cost of the solution converges to the optimal cost as samples → ∞.
RRT: NOT asymptotically optimal (gets stuck in local minima).
RRT*, PRM*: ARE asymptotically optimal.
"RRT* konverguje k optimu, RRT ne."
RRT: NOT asymptotically optimal (gets stuck in local minima).
RRT*, PRM*: ARE asymptotically optimal.
"RRT* konverguje k optimu, RRT ne."
5. Describe RRT algorithm steps.
- Sample random configuration qrand
- Find nearest node qnear in tree
- Steer: extend towards qrand by step Δq
- If collision-free, add new node to tree
- Repeat until goal reached
6. How does RRT* differ from RRT?
Two key additions:
- Best parent selection: Check all neighbors within radius r, choose one giving lowest cost.
- Rewiring: After adding node, check if routing through it reduces cost for neighbors.
7. What is RRG (Rapidly-exploring Random Graph)?
Like RRT but maintains a graph instead of tree.
New nodes connect to ALL neighbors within radius (not just best parent).
More edges = more path options, but higher memory.
"Graf místo stromu - více hran, více cest."
"Graf místo stromu - více hran, více cest."
8. What are Informed RRT* and RABIT*?
Informed RRT*: After finding initial path, samples only within ellipsoidal heuristic region that could improve cost.
RABIT*: Regionally Accelerated BIT* - combines batch sampling with heuristic guidance.
"Informované vzorkování v elipse možného zlepšení."
RABIT*: Regionally Accelerated BIT* - combines batch sampling with heuristic guidance.
"Informované vzorkování v elipse možného zlepšení."
Nodes: 0
Path Cost: -
Ready
What is it? Planning problems involving visiting multiple goal locations, optimizing order and/or paths.
TSP: Visit all cities exactly once, minimize distance. TSPN: Visit regions instead of exact points. Dubins: Curved paths for vehicles with turning constraints.
Multi-Goal & TSP Planning
What is it? Planning problems involving visiting multiple goal locations, optimizing order and/or paths. Related to the classic Traveling Salesman Problem.
TSP Traveling Salesman Problem
Problem: Visit ALL n cities exactly once and return to start, minimizing total distance.
- Input: Set of n points (cities)
- Output: Optimal tour (permutation)
- Complexity: NP-hard, O(n!) brute force
✏️ Sketch: Points connected in a loop, forming closed tour through all cities.
TSPN TSP with Neighborhoods
Key difference: Don't visit exact points - visit regions (neighborhoods).
- Each goal is a disk/polygon region
- Robot must enter each region (anywhere inside)
- Optimizes both order and entry points
✏️ Sketch: Circles (regions) connected by path that touches edge of each circle, not center.
Dubins Vehicle Curvature-Constrained
What is it? Vehicle that can only move forward with bounded turning radius ρmin.
- Config: (x, y, θ) - position + heading
- Dubins curves: Shortest path is always CSC or CCC (C=arc, S=straight)
- 6 types: LSL, RSR, LSR, RSL, RLR, LRL
✏️ Sketch: Show car with turning circles. Path = arc + line + arc.
SOM Solver Self-Organizing Map
Idea: Neural network approach to approximate TSP solution.
- Ring of neurons representing tour
- Learning: Present random city, pull nearest neuron and neighbors toward it
- Ring gradually wraps around all cities
- Fast approximation, not guaranteed optimal
✏️ Sketch: Elastic ring deforming to pass through scattered points.
Key Formulas
Euclidean TSP: dist = √[(x₂-x₁)² + (y₂-y₁)²]
Dubins length: L = ρ·(|α| + |β|) + d (for CSC)
SOM update: wi += η·h(i,winner)·(city - wi)
Dubins length: L = ρ·(|α| + |β|) + d (for CSC)
SOM update: wi += η·h(i,winner)·(city - wi)
Controls
Dubins Demo
Guide
Multi-Goal Solver
Algorithm: Self-Organizing Map (SOM)
Problem Type
Vehicle Model
Status
Tour Length: 0
Neurons: 0
Add targets by clicking the map.
Dubins Path Demo
Interactive visualization of Dubins curves
Turning Radius
50
How to use:
Left click: Set START position & heading
Right click: Set GOAL position & heading
Drag: Adjust heading direction
Current Path: RSR
Length: 0 units
Legend:
Start config (S)
Goal config (G)
Left turning circle
Right turning circle
Arc segment
Straight segment
What you're seeing:
Each configuration has 2 turning circles (left & right). The Dubins path uses arcs on these circles connected by a straight tangent line.
CSC = arc + straight + arc
CCC = arc + arc + arc (no straight)
Exam Questions & Answers
1. Main differences between TSP and TSPN?
TSP: Visits specific points. Optimization of order only.
TSPN: Visits regions (neighborhoods). Optimization of order AND specific location within region.
"TSP navštěvuje body, TSPN navštěvuje regiony/okolí."
TSPN: Visits regions (neighborhoods). Optimization of order AND specific location within region.
"TSP navštěvuje body, TSPN navštěvuje regiony/okolí."
2. Describe the Dubins vehicle model.
A kinematic model with:
"Konstantní rychlost, omezený poloměr otáčení."
- Constant forward speed v
- Limited turning radius ρ (cannot turn on spot)
- State: (x, y, θ) - position and heading
ẋ = v·cos(θ), ẏ = v·sin(θ), θ̇ = u/ρ"Konstantní rychlost, omezený poloměr otáčení."
3. What is the optimal Dubins path?
Shortest path between two states (x,y,θ) consists of at most 3 segments:
CSC: Curve-Straight-Curve (e.g., LSL, RSR, LSR, RSL)
CCC: Curve-Curve-Curve (e.g., LRL, RLR)
L=Left turn, R=Right turn, S=Straight
"Maximálně 3 segmenty: oblouky a přímky."
CSC: Curve-Straight-Curve (e.g., LSL, RSR, LSR, RSL)
CCC: Curve-Curve-Curve (e.g., LRL, RLR)
L=Left turn, R=Right turn, S=Straight
"Maximálně 3 segmenty: oblouky a přímky."
4. Ordinary TSP vs Dubins TSP?
Ordinary TSP: Euclidean distance (straight lines). Heading irrelevant. Symmetric distances.
Dubins TSP: Distance depends on position AND heading (θ). Paths are curves. Asymmetric! d(A→B) ≠ d(B→A)
"DTSP závisí na poloze i směru, asymetrické vzdálenosti."
Dubins TSP: Distance depends on position AND heading (θ). Paths are curves. Asymmetric! d(A→B) ≠ d(B→A)
"DTSP závisí na poloze i směru, asymetrické vzdálenosti."
5. Formal Multi-Goal Planning Problem?
Find trajectory σ(t) on [0, T] such that for every goal region Ri, ∃ti where σ(ti) ∈ Ri.
Admissible solution: Visits all goals, respects robot constraints.
Objective: Minimize total path length or time T.
"Trajektorie navštíví všechny regiony."
Admissible solution: Visits all goals, respects robot constraints.
Objective: Minimize total path length or time T.
"Trajektorie navštíví všechny regiony."
6. SOM for TSP/TSPN?
Self-Organizing Map: ring of neurons adapts to targets.
- Winner: Neuron closest to selected target
- Update: Winner + neighbors move toward target
- TSPN mod: Attract to closest point in region, not center
7. Define Generalized TSP (GTSP)?
Given clusters of cities, visit exactly one city from each cluster.
Noon-Bean transformation: Convert GTSP to Asymmetric TSP by adding zero-cost edges within clusters.
"Navštiv právě jeden bod z každého clusteru."
Noon-Bean transformation: Convert GTSP to Asymmetric TSP by adding zero-cost edges within clusters.
"Navštiv právě jeden bod z každého clusteru."
8. TSP Approximation Algorithms?
Nearest Neighbor: Greedy, O(n²), factor ≈ log(n)
Christofides: MST + matching + Eulerian, 3/2-approximation for metric TSP
2-opt, 3-opt: Local search improvements
"Christofides garantuje 1.5× optimum."
Christofides: MST + matching + Eulerian, 3/2-approximation for metric TSP
2-opt, 3-opt: Local search improvements
"Christofides garantuje 1.5× optimum."
9. Orienteering Problem (OP)?
TSP: Visit ALL goals, minimize cost
OP: Budget constraint B, maximize collected prizes
Goals have prizes pi. Find route with total length ≤ B maximizing Σpi.
"Rozpočet na cestu, maximalizuj zisk."
OP: Budget constraint B, maximize collected prizes
Goals have prizes pi. Find route with total length ≤ B maximizing Σpi.
"Rozpočet na cestu, maximalizuj zisk."
10. Dubins Touring Problem (DTP)?
Visit sequence of goals with Dubins vehicle. Order is fixed, optimize entry headings.
Solution: Discretize headings at each goal, build graph, find shortest path.
Lower bound: Sum of minimum Dubins distances between consecutive goals.
"Pořadí dané, optimalizuj směry příjezdu."
Solution: Discretize headings at each goal, build graph, find shortest path.
Lower bound: Sum of minimum Dubins distances between consecutive goals.
"Pořadí dané, optimalizuj směry příjezdu."
11. DTSPN - Dubins TSP with Neighborhoods?
Combine Dubins vehicle constraints with region visits.
Approaches:
Approaches:
- Decoupled: Solve TSPN first, then optimize Dubins paths
- Sampling: Sample boundary points, solve as DTSP
- SOM-based: Adapted neural network approach
12. Decoupled vs Coupled approaches?
Decoupled: Solve subproblems separately (e.g., TSP order first, then path planning). Faster but suboptimal.
Coupled: Solve jointly considering all constraints. Better solutions but harder.
"Decoupled = rychlejší, Coupled = lepší řešení."
Coupled: Solve jointly considering all constraints. Better solutions but harder.
"Decoupled = rychlejší, Coupled = lepší řešení."
What is it? Discretize continuous space into a grid. Each cell is free or occupied. Plan by searching the grid graph.
A*: f(n)=g(n)+h(n), optimal with admissible heuristic. Theta*: Any-angle paths via line-of-sight checks. JPS: Faster A* by pruning symmetric paths.
Grid-Based Planning
What is it? Discretize continuous space into a grid (occupancy map). Each cell is free or occupied. Plan by searching the grid graph.
A* Optimal Graph Search
Core formula:
Optimal if: h(n) is admissible (never overestimates).
f(n) = g(n) + h(n)
- g(n): Actual cost from start to n
- h(n): Heuristic (estimated cost to goal)
- f(n): Total estimated cost through n
Optimal if: h(n) is admissible (never overestimates).
✏️ Sketch: Grid with open set (frontier) and closed set (visited). Arrows showing expansion.
Theta* Any-Angle Planning
Problem with A*: Paths constrained to grid edges (zigzag).
Theta* fix: Check line-of-sight to grandparent.
- If parent's parent is visible → connect directly (shortcut)
- Results in smoother, shorter paths
if lineOfSight(parent(s), s'): parent(s') = parent(s)
✏️ Sketch: Show A* zigzag vs Theta* diagonal shortcut.
D* Lite Incremental Replanning
Key idea: Efficiently replan when map changes (dynamic environments).
- g(s): Current cost estimate
- rhs(s): One-step lookahead cost
- Consistent: g(s) = rhs(s)
- Inconsistent: g(s) ≠ rhs(s) → needs update
✏️ Sketch: Show obstacle appearing, only nearby nodes being updated.
JPS Jump Point Search
Key idea: A* optimization for uniform-cost grids. Prunes symmetric paths by "jumping" over intermediate nodes.
- Jump Points: Nodes where path direction must change
- Forced Neighbors: Neighbors that become relevant due to obstacles
- Pruning: Skip nodes reachable optimally via parent
✏️ Sketch: Show jumping over empty cells, stopping at forced neighbors.
Key Concepts C-Space & More
Configuration Space (C): All possible robot poses.
Cfree: Collision-free configurations.
Minkowski Sum: For disk robot radius r, expand obstacles by r.
Distance Transform: Each cell stores distance to nearest obstacle (brushfire algorithm).
Visibility Graph: Connect visible obstacle corners → shortest polygonal path.
Cfree: Collision-free configurations.
Minkowski Sum: For disk robot radius r, expand obstacles by r.
Distance Transform: Each cell stores distance to nearest obstacle (brushfire algorithm).
Visibility Graph: Connect visible obstacle corners → shortest polygonal path.
Heuristics
Euclidean: √[(Δx)² + (Δy)²] - admissible
Manhattan: |Δx| + |Δy| - admissible for 4-connected
Diagonal: max(|Δx|, |Δy|) + (√2-1)·min(|Δx|, |Δy|)
Manhattan: |Δx| + |Δy| - admissible for 4-connected
Diagonal: max(|Δx|, |Δy|) + (√2-1)·min(|Δx|, |Δy|)
Planning
C-Space
Dist Trans
Vis Graph
Guide
Grid Planner
Algorithm
Left Click: Toggle Wall (Trigger Replanning)
Right Click: Move Start
Shift + Click: Move Goal
1. Pop Lowest F Node (Pick Best)
2. Check if Goal Reached
3. Expand Neighbors (Explore)
3a. Check Line-of-Sight (Theta*)
4. Update Costs & Parent
Jump Point Search: Prunes symmetric paths
1. Pop Lowest F Node
2. Check if Goal Reached
3. Identify Successors (Jump)
4. Find Jump Points
5. Update Costs & Parent
Backward Search: Goal → Start
1. Pop Min Key (Priority Queue)
2. Consistency Check (g vs rhs)
3. Update Neighbors (Predecessors)
4. Update Keys & Re-insert
Results
Path Cost: 0
Visited Nodes: 0
Ready
Configuration Space
Workspace → C-space transformation
Robot Radius
2
View
Legend:
Original Obstacle
C-obstacle (expanded)
Robot (disk)
Robot in C-space (point)
How C-space works:
For a disk robot with radius r, obstacles are expanded by r (Minkowski sum).
The robot becomes a point in C-space. If the point is in Cfree, the disk robot doesn't collide.
"Překážky se zvětší o poloměr robota."
Distance Transform
Brushfire algorithm visualization
Distance Color Scale:
0 (Obstacle)
Max Distance
View Mode
Watch wavefront expand from obstacles
Max Distance: 0 cells
Safest Point: (0, 0)
What is Distance Transform?
Each cell stores distance to nearest obstacle.
Brushfire Algorithm: BFS wavefront from all obstacles simultaneously. Layer by layer expansion.
Applications:
- Path planning with clearance (stay away from walls)
- Voronoi diagram approximation (ridges = equidistant)
- Navigation functions
"Vzdálenost ke stěnám pro bezpečné plánování."
Visibility Graph & Voronoi
Geometric path planning methods
View Mode
Visibility Graph Legend:
Vertex (obstacle corner)
Visibility edge
Shortest path
Start
Goal
Voronoi Diagram Legend:
Voronoi edge (equidistant)
Path along Voronoi
Obstacle
Voronoi edges maximize clearance from obstacles
What is a Visibility Graph?
Vertices: Start, Goal, and all obstacle corners (convex hull vertices).
Edges: Connect vertices if the line segment doesn't intersect any obstacle interior.
Shortest path: Run Dijkstra/A* on the graph. The result is the optimal path among all polygonal paths.
Complexity: O(n² log n) where n = number of vertices.
"Spojíme viditelné rohy - nejkratší cesta je na hranách."
What is a Voronoi Diagram?
Definition: Partitions space into regions closest to each obstacle.
Edges: Points equidistant from two or more obstacles.
For path planning: Path along Voronoi edges maximizes clearance from obstacles (safest path).
Approximation: Ridge detection on Distance Transform gives Voronoi-like skeleton.
"Voroného diagram = maximální vzdálenost od překážek."
Vis Graph vs Voronoi:
| Vis Graph: | Shortest path, touches obstacles |
| Voronoi: | Safest path, max clearance |
Exam Questions & Answers
1. Define C and Cfree.
C (Configuration Space): The set of all possible poses (configurations) of the robot.
Cfree: The subset of C where the robot does not collide with obstacles.
Cobs: C \ Cfree - configurations in collision.
"C = všechny pózy, Cfree = pózy bez kolize."
Cfree: The subset of C where the robot does not collide with obstacles.
Cobs: C \ Cfree - configurations in collision.
"C = všechny pózy, Cfree = pózy bez kolize."
2. What is a path vs trajectory?
Path: A continuous curve σ: [0,1] → Cfree from start to goal. No time information.
Trajectory: A path with timing information σ(t), specifying when robot is at each configuration.
"Cesta = geometrie, trajektorie = cesta + čas."
Trajectory: A path with timing information σ(t), specifying when robot is at each configuration.
"Cesta = geometrie, trajektorie = cesta + čas."
3. Characterize grid-based planning?
Methods that discretize the continuous world into a grid (matrix). The problem is converted into a graph search (nodes = cells, edges = adjacency). Standard algorithms like A* or Dijkstra are used.
"Diskretizace světa na mřížku + prohledávání grafu."
"Diskretizace světa na mřížku + prohledávání grafu."
4. A* Algorithm - f(n) = g(n) + h(n)
g(n): Cost from start to node n (actual)
h(n): Heuristic estimate from n to goal
f(n): Total estimated cost through n
A* expands node with lowest f(n). Optimal if h is admissible (never overestimates).
"f = g + h, vybíráme nejmenší f."
h(n): Heuristic estimate from n to goal
f(n): Total estimated cost through n
A* expands node with lowest f(n). Optimal if h is admissible (never overestimates).
"f = g + h, vybíráme nejmenší f."
5. Sketch Theta* vs A*.
A*: Path constrained to grid edges (zigzag).
Theta*: "Any-angle" planning. Checks line-of-sight to the parent's parent. If visible, creates shortcut diagonal edge.
"Theta* vidí 'zkratku' přes souseda."
Theta*: "Any-angle" planning. Checks line-of-sight to the parent's parent. If visible, creates shortcut diagonal edge.
if lineOfSight(parent(s), s'):
parent(s') = parent(s)"Theta* vidí 'zkratku' přes souseda."
5b. What is Jump Point Search (JPS)?
A* optimization for uniform-cost grids that prunes symmetric paths.
Key concepts:
Same optimal path as A*, but explores far fewer nodes.
"Skáče přes prázdné buňky, zastaví u překážek."
Key concepts:
- Jump Points: Nodes where direction must change
- Forced Neighbors: Neighbors revealed by obstacles
- Pruning: Skip nodes reachable via parent
Same optimal path as A*, but explores far fewer nodes.
"Skáče přes prázdné buňky, zastaví u překážek."
6. Main idea of D* Lite?
Incremental heuristic search for dynamic environments.
Key concepts:
"Inkrementální - přepočítá jen nutné minimum."
Key concepts:
- g(s): Current cost estimate
- rhs(s): One-step lookahead cost
- Consistent: g(s) = rhs(s)
- Inconsistent: g(s) ≠ rhs(s) → needs update
"Inkrementální - přepočítá jen nutné minimum."
7. What is Bresenham's line algorithm?
Efficient algorithm to determine which grid cells a line passes through.
Used in path planning for:
- Line-of-sight checks (Theta*)
- Collision detection on grids
- Ray casting for sensor simulation
8. What is Distance Transform?
Computes distance from each free cell to nearest obstacle.
For path planning: Propagate distance from goal, then follow gradient descent.
Benefits: Simple, no explicit graph needed.
Drawback: May not find optimal path on discretized grid.
"Vzdálenost od překážek → gradient k cíli."
Benefits: Simple, no explicit graph needed.
Drawback: May not find optimal path on discretized grid.
"Vzdálenost od překážek → gradient k cíli."
9. Jump Point Search (JPS)?
Optimization of A* for uniform-cost grids.
Key idea: Skip intermediate nodes by "jumping" to important points (corners, direction changes).
Much faster than A* on large open grids - same optimality.
"Přeskakuje nudné uzly, hledá důležité body."
"Přeskakuje nudné uzly, hledá důležité body."
10. Visibility Graph vs Voronoi Diagram?
Visibility Graph: Connects obstacle vertices if visible. Shortest path but close to obstacles.
Voronoi Diagram: Path maximally far from all obstacles. Safer but longer path.
"Visibility = nejkratší, Voronoi = nejbezpečnější."
Voronoi Diagram: Path maximally far from all obstacles. Safer but longer path.
"Visibility = nejkratší, Voronoi = nejbezpečnější."
What is it? Robot explores unknown environment, building a map while deciding where to go next.
Occupancy Grid: Probabilistic map with P(occupied). Frontiers: Boundaries between known and unknown space. D* Lite: Incremental replanning for changing environments.
Autonomous Exploration
What is it? Robot explores unknown environment, building a map while deciding where to go next. Combines mapping, localization, and planning.
Occupancy Grid Probabilistic Map
Idea: Grid where each cell stores probability of being occupied.
- P(m) = 0.5: Unknown
- P(m) → 1: Likely occupied
- P(m) → 0: Likely free
l(m) = log(P(m)/(1-P(m)))
✏️ Sketch: Grid with cells colored: black=occupied, white=free, gray=unknown.
Sensor Models Laser vs Sonar
Laser (narrow beam):
- Cells along ray → decrease P(occupied)
- Cell at endpoint → increase P(occupied)
- High accuracy, narrow cone
- Wide cone of uncertainty
- Can't tell exactly where obstacle is within cone
- Multiple readings needed to narrow down
✏️ Sketch: Laser = thin line. Sonar = wide cone/arc.
Frontier-Based Exploration Strategy
Frontier: Boundary between known-free and unknown regions.
- Detect frontier cells (free cell adjacent to unknown)
- Cluster frontiers into regions
- Select best frontier (nearest, largest, most info gain)
- Plan path to frontier, execute, repeat
✏️ Sketch: Map with known area, frontier cells highlighted at boundary with gray (unknown).
Information Gain Smart Selection
Problem: Which frontier to visit?
- Nearest: Minimize travel (greedy)
- Largest: More area to explore
- Info gain: Expected reduction in map entropy
- Combined: gain/cost ratio
Key Terms
SLAM: Simultaneous Localization And Mapping
Ray casting: Trace sensor beam through grid
Coverage: % of environment mapped
Next-Best-View: Where to look next for max info
Ray casting: Trace sensor beam through grid
Coverage: % of environment mapped
Next-Best-View: Where to look next for max info
Simulation
Topic Guide
Frontier Exploration
Occupancy Grid + Frontier-based
Sensor
Click canvas: Move robot to location
Play: Auto-explore (find frontiers)
Reset: New random environment
1. Sense Environment (Ray cast)
2. Update Occupancy Grid
3. Detect Frontiers
4. Select Best Frontier
5. Navigate to Frontier
Legend:
Obstacle
Free
Unknown
Frontier
Stats
Explored: 0%
Frontiers: 0
Ready
Exam Questions & Answers
1. What is an Occupancy Grid Map?
Grid representation where each cell stores probability of being occupied.
- P(occupied) = 0 → definitely free
- P(occupied) = 1 → definitely obstacle
- P(occupied) = 0.5 → unknown
2. Occupancy Grid Assumptions?
- Cells are completely free OR occupied (binary)
- Cells are independent of each other
- Environment is static
3. Sonar vs Laser Sensor Model?
Sonar: Wide beam angle (cone), lower accuracy, can detect glass.
Laser: Narrow beam, high accuracy, may miss transparent objects.
Update: Use log-odds for numerical stability.
"Sonar = široký kužel, Laser = úzký paprsek."
Laser: Narrow beam, high accuracy, may miss transparent objects.
Update: Use log-odds for numerical stability.
"Sonar = široký kužel, Laser = úzký paprsek."
4. What is a Frontier?
Boundary between known free space and unknown space.
Frontiers represent areas worth exploring.
"Hranice mezi známým volným a neznámým prostorem."
Frontiers represent areas worth exploring.
"Hranice mezi známým volným a neznámým prostorem."
5. Frontier-based Exploration Algorithm?
- Sense and update map
- Detect frontier cells
- Cluster frontiers into regions
- Select best frontier (size, distance, info gain)
- Navigate to selected frontier
- Repeat until no frontiers remain
6. Multi-robot Exploration Challenges?
- Task allocation (who explores where?)
- Map merging and alignment
- Communication constraints
- Avoiding redundant exploration
7. Multi-robot Exploration Strategies?
Market-based: Robots bid on frontiers, auction assigns tasks.
Potential field: Robots repel each other, attract to frontiers.
Greedy assignment: Each robot takes nearest unassigned frontier.
"Aukce, potenciálová pole, nebo greedy přiřazení."
Potential field: Robots repel each other, attract to frontiers.
Greedy assignment: Each robot takes nearest unassigned frontier.
"Aukce, potenciálová pole, nebo greedy přiřazení."
8. Log-odds Update for Occupancy?
l(m|z) = l(m|zt) + l(m) - l0Where l = log(p/(1-p)). Avoids numerical issues with multiplying small probabilities.
"Log-odds pro numerickou stabilitu."
9. Information Gain in Exploration?
Expected reduction in uncertainty (entropy) from visiting a frontier.
Frontiers with high information gain are preferred.
"Očekávané snížení entropie mapy."
IG(f) = H(map) - H(map | visit f)Frontiers with high information gain are preferred.
"Očekávané snížení entropie mapy."