Introduction
Pathfinding是在平面上两点之间找出路径的问题。也是机器人和人工智能的基本算法问题。当然，最常见的pathfinding问题的使用场景是游戏设计。
Requirement
Pathfinding is the problem of finding a path between two points on a plane. It is a fundamental task in robotics and AI. Perhaps the most obvious usage of pathfnding is in computer games, when an object is instructed to move from its current position to a goal position, while avoiding obstacles (e.g., walls, enemy fire) along the way.
Pathfinding in commercial games is frequently accomplished using search algorithms. We consider a simplified version in this assignment. The following shows a 2D map drawn using ASCII characters:
1 1 1 1 1 1 4 7 8 X
1 1 1 1 1 1 1 5 8 8
1 1 1 1 1 1 1 4 6 7
1 1 1 1 1 X 1 1 3 6
1 1 1 1 1 X 1 1 1 1
1 1 1 1 1 1 1 1 1 1
6 1 1 1 1 X 1 1 1 1
7 7 1 X X X 1 1 1 1
8 8 1 1 1 1 1 1 1 1
X 8 7 1 1 1 1 1 1 1
Given a start position and an end position on the map, our aim is to find a path from the start position to the end position. The character “X” denotes an obstacle that cannot be traversed by a path, while the digits represent the elevation at the respective positions.
Any position is indicated by the coordinates (i, j), where i is the row number (ordered top to bottom) and j is the column number (ordered left to right). For example, the top left position is (1, 1), the bottom right is (10, 10), while the position with elevation “3” is (4, 9). Given start position (1, 1) and end position (10, 10), a possible path is
* * * 1 1 1 4 7 8 X
1 1 * 1 1 1 1 5 8 8
1 1 * * * * * * * 7
1 1 1 1 1 X 1 1 * 6
1 1 1 1 1 X 1 * * 1
1 1 1 1 1 1 1 * 1 1
6 1 1 1 1 X 1 * * *
7 7 1 X X X 1 1 1 *
8 8 1 1 1 1 1 1 1 *
X 8 7 1 1 1 1 1 1 *
Note that we use 4-connectedness for paths, which means any two points on the path are only connected if they are vertically or horizontally (but not diagonally!) adjacent.
Problem formulation
Following the lecture notes, we formulate the problem as follows:
- States: Any obstacle-free position (i; j) on the map.
- Initial state: A position (i0, j0) given by the user.
- Actions: Since we consider 4-connectedness, only four actions are available: Up, down, left and right (your program must expand each node in this order). Available actions for positions adjacent to the map boundary or obstacles are reduced accordingly.
- Transition model: Moving left moves the current position to the left, etc.
- Goal test: Check if the current state is the end position (i, j) given by the user.
- Path cost: Given a map M and a path P = {(i0, j0), (i1, j1), … ,(iN, jN)}, the cost of the path is calculated. In words, the cost of a path is the sum of the costs between two adjacent points of the path, and the cost between adjacent points is 1 plus the difference between the elevation of the two points if we climb “uphill”, or simply 1 if we stay “level” or slide “downhill”.
This means shorter paths which avoid climbing cost less. As an example, the cost in the path in the previous page is 25. What is the optimal (cheapest) path?
Your Task
Solve pathfinding using Breadth-First Search (BFS), Uniform-Cost Search (UCS) and A Search. You should base your program on the pseudocode GRAPH-SEARCH in the lecture slides, and carefully think about the appropriate data structures to use. For A Search, you must implement two heuristics:
- Euclidean distance between current position and end position.
- Manhattan distance between current position and end position.
For the map in Page 1 with start position (1, 1) and end position (10, 10), your program should help you answer these questions:
- Are the paths returned by the three methods different?
- What about the optimality of the returned paths?
- Which method is the most computationally and memory efficient?
- Do the two heuristics for A* Search provide different solutions?
- Does checking for repeated states matter in this problem?