Assignment 1

Part 1 Pathfinding

Pathfinding is the problem of finding a path between two points on a plane. It is a fundamentaltask in robotics and AI. Perhaps the most obvious usage of pathfinding is in computer games,when an object is instructed to move from its current position to a goal position, while avoidingobstacles (e.g., walls, enemy fire) along the way. Pathfinding in commercial games is frequently accomplished using search algorithms . Weconsider a simplified version in this assignment. The following shows a 2D map drawn usingASCII 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 startposition to the end position. The character 'X' denotes an obstacle that cannot be traversed by apath, 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 tobottom) 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 onlyconnected 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 States: A position (i j ) given by the user.
• Actions: Since we consider 4-connectedness, only four actions are available: Up, down, leftand right (your program must expand each node in this order). Available actions forpositions 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.

and M(a, b) is the elevation at the position (a, b). In words, the cost of a path is the sum of thecosts between adjacent points in the path, and the cost between adjacent points is 1 plus thedifference 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 inthe previous page is 25. What is the optimal (i.e., cheapest) path?

Your Tasks

Solve this pathfinding task using three different methods:

• Breadth First Search (BFS)
• Uniform Cost Search (UCS)
• A* Search (A*)

You should base your program on the pseudocode GRAPH-SEARCH in the lecture slides, andcarefully think about the appropriate data structures to use. A* search requires a heuristic . In thisassignment, you must implement two such heuristics

• .The Euclidean distance between current position and end position.
• The Manhattan distance between the current position and end position. For the map above with start position (1, 1) and end position (10, 10), your program should helpyou answer these questions:
• 1. Are the paths returned by the three methods different?
• 2. What about the optimality of the returned paths?
• 3. Which method is the most computationally and memory efficient?
• 4. Do the two heuristics for A* Search provide different - solutions?
• 5. Does checking for repeated states matter in this problem?

Deliverables

Write your pathfinding program in Python 3.6.9 in a file called pathfinder.py . Your program mustbe able to run as follows:

>>> python pathfinder.py [map] [algorithm] [heuristic]