Explain this informed Search in Grid Type Environment---**Title:**
Informed Search in Grid-Type Environment
**General Information:**
We say an algorithm is **informed** if it relies on problem-specific knowledge that helps us decide which node to expand next.
One approach for making a search informed is to add a **heuristic function** — h(n) — that estimates cost-to-go: from any node n to the current goal.
**Chart/Diagram Description: (A) 4-connected gridmap**
* **Type:** Grid Diagram
* **Main Elements:** A 3x3 grid represents a gridmap.
* A black circular point (labeled 'Robot' above) is located in the center cell (row 2, column 2).
* Arrows indicate connections from the center cell to its four immediate neighbors:
* An arrow points upwards to the cell (row 1, column 2), labeled '1'.
* An arrow points leftwards to the cell (row 2, column 1), labeled '2'.
* An arrow points downwards to the cell (row 3, column 2), labeled '3'.
* An arrow points rightwards to the cell (row 2, column 3), labeled '4'.
* The diagram is annotated as a "4-connected gridmap".
**Table Content:**
A 5x8 grid table showing numerical values, a circled number, and a star symbol.
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 3 |
|---|---|---|---|---|---|---|---|
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 2 |
| 6 | 5 | (4) | 3 | 2 | 1 | ☆ | 1 |
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 2 |
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 3 |
* **Annotation:** The number '4' in the third row, third column is enclosed in a blue circle. A star symbol (☆) is in the third row, seventh column.
**Mathematical Formulas/Heuristic Functions:**
* **Manhattan Distance:**
* Description: Use Manhattan distance from current state to the goal as heuristic function
* Formula: `h_M(n) = Δx + Δy`
* **Straight-line distance (Euclidean distance):**
* Description: Straight-line distance (Euclidean distance):
* Formula: `h_SLD = √Δx² + Δy²`
**Question:**
Which h(n) is more informed for this agent?
**Page Number:**
4
视频信息
答案文本
视频字幕
Search algorithms can be classified as uninformed or informed. Uninformed search algorithms like breadth-first search explore nodes blindly without any problem-specific knowledge. In contrast, informed search algorithms use heuristic functions to estimate the cost from any node to the goal, making the search more efficient and directed.
Grid-type environments are common in robotics and pathfinding problems. In a 4-connected gridmap, the agent can only move to four adjacent cells: up, down, left, and right. Diagonal movements are not allowed. This constraint is important because it affects which heuristic functions will be most accurate for estimating distances.
Manhattan distance is a heuristic function that calculates the sum of horizontal and vertical distances between two points. In our grid example, the robot at position marked with a circle needs to reach the goal marked with a star. The Manhattan distance is calculated as delta x plus delta y, which equals 4 plus 0, giving us a total distance of 4. This represents the minimum number of moves needed in a 4-connected grid.
Euclidean distance calculates the straight-line distance between two points using the Pythagorean theorem. In our example, we form a right triangle where delta x equals 4 and delta y equals 0. The Euclidean distance is the square root of delta x squared plus delta y squared, which equals the square root of 16 plus 0, giving us 4. While this matches the Manhattan distance in this specific case, Euclidean distance generally underestimates the true path cost in grid environments where diagonal movement is not allowed.
When comparing heuristic accuracy in 4-connected grids, Manhattan distance proves more informed than Euclidean distance. Manhattan distance provides exact estimates because it matches the actual movement constraints - you can only move horizontally and vertically. In contrast, Euclidean distance often underestimates the true cost because it assumes diagonal movement is possible. For example, when moving diagonally across the grid, Euclidean distance gives a shorter estimate than the actual path length required. Therefore, Manhattan distance is more informed for this type of environment.