Assignment Instructions:

Teams: Assignments should be completed by groups of students (up to 3 - from any section). No additional credit will be given for students working individually or in groups of 2.  You are encouraged to form a team of three students.  Please inform the TAs as soon as possible about the members of your team so they can update the scoring spreadsheet and no later than Monday, January 31. Only one member of the team should submit the assignment.  You can use the following Google form: https://forms.gle/bqUWCeFWzR3fSn5N8. You can also find the TAs’contact information on the course’s syllabus, or contact them via Discord.

Report Submission Rules: Submit your reports electronically as a PDF document through Cavnas.   For your reports, do not submit Word documents, raw text, or hardcopies etc. Make sure to generate and submit a PDF instead regardless of how you generated the material. Each team of students should submit only a single copy of their solutions and indicate all team members (name, netID and section) on their submission .

Program Evaluation: For the programming component, you need to also submit a compressed file via Canvas, which contains your results and/or code as requested by the assignment. You will need to make sure that your program is executable by the TAs by following the instructions indicated here.

Late Submissions: No late submissions are allowed with the exception of extreme circumstances.  Any delay in submitting the assignment will impact your ability to prepare for the midterm.

Start working on the assignment early!

Extra Credit for LATEX: You will receive 6% extra credit points if you submit your answers as a typeset PDF (i.e., one that has been prepared by using TEX,  in which case you should also submit electronically the source TEXcode for the report).  Resources on how to use TEX will be made available on the course’s website.  There will be a 3% bonus for electronically prepared answers (e.g., on MS Word, etc.), which are not typeset with TEX. The bonuses are computed as functions of your score, i.e., if you were to receive 50 points out of 100 and you typesetted your answer with TEX, then you will get a score of 52.  If you want to submit a handwritten report, scan it and submit a PDF but you will not receive any extra credit points. If you choose to submit PDFs of handwritten answers and we are not able to read them, you will not be awarded any points for the part of the solution that is unreadable. We will not accept hardcopy submissions.

Precision: Try to be precise in your description and thorough in your evaluation. Have in mind that you are trying to convince a very skeptical reader (and computer scientists are the worst kind...) that your answers are correct.

Collusion, Plagiarism, etc. : Each  team  must  prepare  its  solutions  independently  from  other  teams, i.e., without using common code,  notes or worksheets with other students or trying to solve problems in collaboration with other teams.  If you are asked to implement an algorithm yourself, you should do so and not use external code.  You must indicate any external sources you have used in the preparation of your solution.  Do not plagiarize online sources and in general make sure you do not violate any of the academic standards of the course, the department or the university (the standards are available through the course’s syllabus). Failure to follow these rules may result in failure in the course.

Problem 1:

Any-Angle Path Planning

70 points + 30 extra credit points

Grids with blocked and unblocked cells are often used to represent terrains in computer games, virtual/augmented reality systems, robotic or human-assistive navigation systems.  For instance, in games, when the human player selects with the mouse a destination for a game character, then a reasonable, short path has to be computed.  Classical search algorithms can find paths on reasonable size grids quickly but these grid paths consist of grid edges and their possible headings are thus artificially constrained, which results in them being longer than minimal and unrealistic looking.  Any-angle path planning avoids this issue by propagating information along grid edges, to achieve small run-times, without constraining the paths to grid edges, to find any- angle paths [1].

1 Project Description

We consider a 2D continuous terrain discretized into a grid of square cells (with side lengths one) that are either blocked or unblocked. We assume that the grid is surrounded by blocked cells. We also assume a static environment (i.e., blocked cells remain blocked and unblocked cells remain unblocked).   We define vertices to be the corner points of the cells,  rather than their centers. Agents are points that can move along (unblocked) paths.   Paths cannot pass through blocked cells or move between two adjacent blocked cells but can pass along the border of blocked and unblocked cells.   For simplicity (but not realism), we assume that paths can also pass through vertices where two blocked cells diagonally touch one another. The objective of path planning is to find a short and realistic looking path from a given unblocked start vertex to a given goal vertex. In this project, all algorithms search uni-directionally from the start vertex to the goal vertex.

1                 2                 3                 4                 5

A

sstart

B

C

sgoal

shortest grid path

1                 2                 3                 4                 5

A

sstart

B

C

sgoal

shortest path

Figure 1: (a) Shortest Grid Path, (b) Shortest Any-Angle Path

Figure 1 provides an example. White cells are unblocked and grey cells are blocked. The start vertex is marked sstart and the goal vertex is marked sgoal . Figure 1(a) shows the grid edges for an eight-neighbor grid (solid black lines) and a shortest grid path (dashed red line). Figure 1(b) shows the shortest any-angle path (dashed red line).  To understand better which paths are unblocked, assume that cell B3-B4-C4-C3 in Figure 1 is also blocked in addition to cells A2-A3-B3-B2 and B4- B5-C5-C4. Then, the path [A1, B2, B3, A3, A5, C1, C2, A4, B5, B1, C3] is unblocked even though it repeatedly passes through a vertex where diagonally touching blocked cells meet. On the other hand, the following  paths are  blocked:  [B4,C4] and [A4,C4] (paths cannot  move  between two adjacent blocked cells), [A2,A3] and [A1,A4] (paths cannot move between two adjacent blocked cells and the grid is surrounded by blocked cells - not shown in the figure), [C3,B4] and [C2,B4] and [C1,B5] (paths cannot pass through blocked cells).

2 Review of the A* algorithm (will be covered in class)

The pseudo-code of A* is shown in Algorithm 1. A* is described in your artificial intelligence textbook, covered during the lectures and therefore described only briefly in the following, using the following notation:

• S denotes the set of vertices.

• sstrt ∈ S denotes the start vertex (= the current point of the agent), and

• sgo ∈ S denotes the goal vertex (= the destination point of the agent).

• c(s, s′ ) is the straight-line distance between two vertices s, s′ ∈ S .

•  Finally, succ(s) ⊆ S is the set of successors of vertex s ∈ S, which are those (at most eight) vertices adjacent to vertex s so that the straight lines between them and vertex s are un- blocked.

Main()

g(sstart) := 0;

parent(sstart) := sstart;

fringe := ∅;

fringe.Insert(sstart, g(sstart) + h(sstart));

closed := ∅;

while fringe ∅ do

s := fringe.Pop();

if s = sgoal then

return “path found”;

closed := closed ∪ {s};

foreach s′ ∈ succ(s) do

if s′ ̸∈ closed then

if s′ ̸∈ fringe then

g(s′ ) := ∞;

UpdateVertex(s, s′ );

UpdateVertex(s,s’)

if g(s) + c(s, s′ ) < g(s′ ) then

g(s′ ) := g(s) + c(s, s′ );

parent(s′ ) := s;

if s′ ∈ fringe then

fringe.Remove(s′ );

fringe.Insert(s′ , g(s′ ) + h(s′ ));

Algorithm 1: A*

For example, the successors of vertex B3 in Figure 1 are vertices A3, A4, B2, B4, C2, C3 and C4. The straight-line distance between vertices B3 and A3 is one, and the straight-line distance between vertices B3 and A4 is p2. A* maintains two values for every vertex s ∈ S :

1. First, the g-value g(s) is the distance from the start vertex to vertex s .

2. Second, the parent parent(s), which is used to identify a path from the start vertex to the goal vertex after A* terminates.

A* also maintains two global data structures:

1. First, the fringe (or open list) is a priority queue that contains the vertices that A* considers to expand. A vertex that is or was in the fringe is called generated. The fringe provides the following procedures:

•  Procedure fringe.Insert(s, ) inserts vertex s with key into the priority queue fringe .

• Procedure fringe.Remove(s) removes vertex s from the priority queue fringe .

•  Procedure fringe.Pop() removes a vertex with the smallest key from priority queue fringe and returns it.

2.  Second,  the closed  list  is a set that contains the vertices that A*  has expanded and en- sures that A* (and, later, Theta*) expand every vertex at most once (i.e., we are executing GRAPH -SEARCH).

A* uses a user-provided constant h-value (= heuristic value) h(s) for every vertex s ∈ S to focus the search, which is an estimate of its goal distance (= the distance from vertex s to the goal vertex). A* uses the h-value to calculate an f-value ƒ (s) = g(s) + h(s) for every vertex s, which is an estimate of the distance from the start vertex via vertex s to the goal vertex.

A* sets the g-value of every vertex to infinity and the parent of every vertex to NULL when it is encountered for the first time [Lines 1-1].  It sets the g-value of the start vertex to zero and the parent of the start vertex to itself [Lines 1-1].  It sets the fringe and closed lists to the empty lists and then inserts the start vertex into the fringe list with its f-value as its priority [1-1].  A* then repeatedly executes the following statements: If the fringe list is empty, then A* reports that there is no path [Line 1]. Otherwise, it identifies a vertex s with the smallest f-value in the fringe list [Line 1].  If this vertex is the goal vertex, then A* reports that it has found a path from the start vertex to the goal vertex [Line 1].  A* then follows the parents from the goal vertex to the start vertex to identify a path from the start vertex to the goal vertex in reverse [not shown in the pseudo-code].  Otherwise, A* removes the vertex from the fringe list [Line 1] and expands it by inserting the vertex into the closed list [Line 1] and then generating each of its unexpanded successors, as follows: A* checks whether the g-value of vertex s plus the straight-line distance from vertex s to vertex s′ is smaller than g-value of vertex s′ [Line 1]. If so, then it sets the g-value of vertex s′ to the g-value of vertex s plus the straight-line distance from vertex s to vertex s′ , sets the parent of vertex s′ to vertex s and finally inserts vertex s′ into the fringe list with its f-value as its priority or, if it was there already, changes its priority [Lines 1-1]. It then repeats the procedure.

Thus, when A* updates the g-value and parent of an unexpanded successor s′ of vertex s in procedure UpdateVertex, it considers the path from the start vertex to vertex s [= g(s)] and from vertex s to vertex s′ in a straight line [= c(s, s′ )], resulting in distance g(s) + c(s, s′ ). A* updates the g-value and parent of vertex s′ if the considered path is shorter than the shortest path from the start vertex to vertex s′ found so far [= g(s′ )].

A* with consistent h-values is guaranteed to find shortest grid paths (optimality criterion).  H- values are consistent (= monotone) iff (= if and only if) they satisfy the triangle inequality, that is, iff h(sgoal ) = 0 and h(s) ≤ c(s, s′ ) + h(s′ ) for all vertices s, s′ ∈ S with s sgoal and s′ ∈ succ(s). For example, h-values are consistent if they are all zero, in which case A* degrades to uniform-first search (or breadth-first search in this case since all the edges have the same cost).

Figure 2: The consistency property for heuristics presented as a triangular inequality.

3 Example Trace of A*

Figure 3 shows a trace of A* with the h-values

h(s) = p2 · min(|s − s|, |sy − sgoal(y)|) + mx(|s − s|, |sy − sgoal(y)|) − min(|s − s|, |sy − sgoal(y)|)                 (1)

to give you data that you can use to test your  implementation. s and sy denote the x- and y-coordinates of vertex s,  respectively.  The labels of the vertices are their f-values (written as the sum of their g-values and h-values) and parents.  (We assume that all numbers are precisely calculated although we round them to two decimal places in the figure.) The arrows point to their parents.  Red circles indicate vertices that are being expanded. A* eventually follows the parents from the goal vertex C1 to the start vertex A4 to identify the dashed red path [A4, B3, C2, C1] from the start vertex to the goal vertex in reverse, which is a shortest grid path.

1                 2                 3                 4                 5

1 00+2 83             0 00+3 83

		A4 1.41+2.41		sstart
				1.00+3.41
		A4		A4

A4

(a)

3

1.41+4.41 A4

4

0.00+3.83

sstart

1.00+3.41

A4

2.83+3.00

B3

(b)

4

1.00+4.83 A4

1.41+4.41 A4

(c)                                                                                                        (d)

Figure 3: Example Trace of A*

4 Theta*

Theta* is a version of A* for any-angle path planning that propagates information along grid edges without constraining the paths to grid edges.  The key difference between the two algorithms is that in Theta* the parent of a vertex can be any other vertex, while in A* the parent of a vertex has to be a successor [2].

Algorithm 2 shows the pseudo-code of Theta*, as an extension of A* in Algorithm 1. Procedure Main is identical to that of A* and thus not shown. Theta* considers two paths instead of only the one path considered by A* when it updates the g-value and parent of an unexpanded successor s′ in procedure UpdateVertex.  In Figure 4, Theta* is in the process of expanding vertex B3 with parent A4 and needs to update the g-value and parent of unexpanded successor C3 of vertex B3. Theta* considers the following two paths: