Description
CS 440: INTRO TO ARTIFICIAL INTELLIGENCE
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 anyangle 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.
s
start
sgoal
shortest grid path
1 2 3 4 5
A
C
B
s
start
sgoal
shortest path
1 2 3 4 5
A
C
B
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 unblocked.
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
′
) := ∞;
parent(s
′
) := NULL;
UpdateVertex(s, s′
);
return “no path found”;
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 p
2. 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 ensures 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). Hvalues 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) = p
2 · min(|s
− s
goal|, |s
y − s
y
goal|) + mx(|s
− s
goal|, |s
y − s
y
goal|) − min(|s
− s
goal|, |s
y − s
y
goal|) (1)
to give you data that you can use to test your implementation. s
and s
y 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.
s
start
sgoal
1 2 3 4 5
A
C
B
A4
A4 A4
A4 A4
A4
1.00+2.83
1.41+2.41 1.00+3.41
1.00+4.83
1.41+4.41
0.00+3.83
(a)
s
start
sgoal
1 2 3 4 5
A
C
B
1.00+4.83
B3
B3 B3
A4
A4 A4
A4 A4
1.00+2.83
1.41+2.41 1.00+3.41 1.41+4.41
2.41+2.00
2.41+1.41
2.83+1.00
0.00+3.83
B3
2.83+3.00
(b)
s
start
sgoal
1 2 3 4 5
A
C
B
1.41+2.41 1.41+4.41 1.00+3.41
2.83+1.00
2.41+1.41
B3
B3 B3
A4
A4 A4
A4 A4
C2
2.41+2.00
C2
4.24+1.00
1.00+2.83 1.00+4.83
3.83+0.00
B3
2.83+3.00
0.00+3.83
(c)
s
start
sgoal
1 2 3 4 5
A
C
B
1.41+2.41 1.41+4.41 1.00+3.41
2.83+1.00
2.41+1.41
B3
B3 B3
A4
A4 A4
A4 A4
C2
2.41+2.00
C2
4.24+1.00
1.00+2.83 1.00+4.83
3.83+0.00
B3
2.83+3.00
0.00+3.83
(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:
UpdateVertex(s,s’)
if LineOfSight(parent(s), s′
) then
/* Path 2 */
if g(parent(s)) + c(parent(s), s′
) < g(s
′
) then
g(s
′
) := g(parent(s)) + c(parent(s), s′
);
parent(s
′
) := parent(s);
if s
′ ∈ open then
open.Remove(s
′
);
open.Insert(s
′
, g(s
′
) + h(s
′
));
else
/* Path 1 */
if g(s) + c(s, s′
) < g(s
′
) then
g(s
′
) := g(s) + c(s, s′
);
parent(s
′
) := s;
if s
′ ∈ open then
open.Remove(s
′
);
open.Insert(s
′
, g(s
′
) + h(s
′
));
Algorithm 2: Theta*
• Path 1: Theta* 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′
) [Line 2]. This
is the path also considered by A*. It corresponds to the dashed red lined from vertex A4 via
vertex B3 to vertex C3 in Figure 4(a).
• Path 2: Theta* also considers the path from the start vertex to the parent of vertex s [=
g(parent(s))] and from the parent of vertex s to vertex s
′
in a straight line [= c(parent(s), s′
)],
resulting in distance g(parent(s)) + c(parent(s), s′
) [Line 2]. This path is not considered by
A* and allows Theta* to construct any-angle paths. It corresponds to the solid blue line from
vertex A4 to vertex C3 in Figure 4(a).
Path 2 is no longer than Path 1 due to the triangle inequality. Thus, Theta* chooses Path 2 over
Path 1 if the straight line between the parent of vertex s and vertex s
′
is unblocked. Figure 4(a)
gives an example. Otherwise, Theta* chooses Path 1 over Path 2. Figure 4(b) gives an example.
Theta* updates the g-value and parent of vertex s
′
if the chosen path is shorter than the shortest
path from the start vertex to vertex s
′
found so far [= g(s
′
)].
s
start
sgoal
1 2 3 4 5
A
C
B
s’
s
Path 1 Path 2
(a) Path 2 is Unblocked
s
start
sgoal
1 2 3 4 5
A
C
B
s
Path 2
s’
Path 1
(b) Path 2 is Blocked
Figure 4: Paths Considered by Theta*
LineOfSight(parent(s), s′
) on Line 2 is true iff the straight line between vertices parent(s) and
s
′
is unblocked. Performing a line-of-sight check is similar to determining which points to plot
on a raster display when drawing a straight line between two points. Consider a line that is
not horizontal or vertical. Then, the plotted points correspond to the cells that the straight line
passes through. Thus, the straight line is unblocked iff none of the plotted points correspond to
LineOfSight(s, s’)
0 := s.;
y0 := s.y;
1 := s
′
.;
y1 := s
′
.y;
ƒ := 0;
dy := y1 − y0;
d := 1 − 0;
if dy < 0 then
dy := −dy;
sy := −1;
else
sy := 1;
if d < 0 then
d := −d;
s := −1;
else
s := 1;
if d ≥ dy then
while 0 ̸= 1 do
ƒ := ƒ + dy;
if ƒ ≥ d then
if grd[0 + ((s − 1)/2), y0 + ((sy − 1)/2)] then
return false;
y0 := y0 + sy;
ƒ := ƒ − d;
if ƒ ̸= 0 AND grd[0 + ((s − 1)/2), y0 + ((sy − 1)/2)] then
return false;
if dy = 0 AND grd[0 + ((s − 1)/2), y0] AND grd[0 + ((s − 1)/2), y0 − 1] then
return false;
0 := 0 + s;
else
while y0 ̸= y1 do
ƒ := ƒ + d;
if ƒ ≥ dy then
if grd[0 + ((s − 1)/2), y0 + ((sy − 1)/2)] then
return false;
0 := 0 + s;
ƒ := ƒ − dy;
if ƒ ̸= 0 AND grd[0 + ((s − 1)/2), y0 + ((sy − 1)/2)] then
return false;
if d = 0 AND grd[0, y0 + ((sy − 1)/2)] AND grd[0 − 1, y0 + ((sy − 1)/2)] then
return false;
y0 := y0 + sy;
return true;
Algorithm 3: Adaptation of the Bresenham Line-Drawing Algorithm
blocked cells. This allows Theta* to perform the line-of-sight checks with standard line-drawing
methods from computer graphics that use only fast logical and integer operations rather than
floating-point operations. Algorithm 3 shows the pseudo-code of such a method, an adaptation
of the Bresenham line-drawing algorithm [3]. s. and s.y denote the x- and y-coordinates of
vertex s, respectively. The value grd[, y] is true iff the corresponding cell is blocked. Note that
the statement grd[0 + ((s − 1)/2), y0 + ((sy − 1)/2)] is equivalent to grd[0 + ((s = 1)?0 :
−1), y0 + ((sy = 1)?0 : −1)] using a conditional expression (similar to those available in C) since s
and sy are either equal to -1 or 1. Floating point arithmetic could possibly result in wrong indices.
5 Example Trace of Theta*
Figure 5 shows a trace of Theta* with the h-values h(s) = c(s, sgoal) to give you data to test your
implementation, similar to the trace of A* from Figure 3. First, Theta* expands start vertex A4, as
shown in Figure 5(a). It sets the parent of the unexpanded successors of vertex A4 to vertex A4.
Second, Theta* expands vertex B3 with parent A4, as in Figure 5(b). The straight line between
unexpanded successor B2 of vertex B3 and vertex A4 is blocked. Theta* thus updates vertex B2
according to Path 1 and sets its parent to vertex B3. On the other hand, the straight line between
unexpanded successors C2, C3 and C4 of vertex B3 and vertex A4 are unblocked. Theta* thus
updates vertices C2, C3 and C4 according to Path 2 and sets their parents to vertex A4. Third,
Theta* expands vertex B2 with parent B3, as in Figure 5(c). (It can also expand C2, since B2 and
C2 have the exact same f-value, and might then find a path different from the one below.) Fourth,
Theta* terminates when it selects the goal vertex C1 for expansion, as in Figure 5(d). Theta* then
follows the parents from the goal vertex C1 to the start vertex A4 to identify the dashed red path
[A4, B3, C1] from the start to the goal in reverse, which is a shortest any-angle path.
s
start
sgoal
1 2 3 4 5
1.00+2.83
1.41+2.24 1.41+4.12
0.00+3.61 1.00+4.47
1.00+3.16
A
C
B
A4
A4 A4
A4 A4
A4
(a)
s
start
sgoal
2.41+1.41
2.83+1.00 2.24+2.00 2.00+3.00
1.00+2.83
1.41+2.24 1.41+4.12
0.00+3.61 1.00+4.47
1.00+3.16
1 2 3 4 5
A
C
B
B3
A4 A4 A4
A4
A4
A4 A4
A4
(b)
s
start
sgoal
3.82+2.00
3.41+1.00
3.65+0.00
2.41+1.41
2.83+1.00 2.24+2.00 2.00+3.00
3.41+2.24 1.00+2.83
1.41+2.24 1.41+4.12
0.00+3.61 1.00+4.47
1.00+3.16
1 2 3 4 5
A
C
B
B3
A4 A4 A4
A4
A4 A4
B3 A4 A4
B2
B3
B2
(c)
s
start
sgoal
1 2 3 4 5
A
C
B
B3
A4 A4 A4
A4
A4 A4
B3 A4
B2
B3
1.00+3.16
A4
3.82+2.00
3.41+1.00
3.65+0.00
2.41+1.41
2.83+1.00 2.24+2.00 2.00+3.00
3.41+2.24 1.00+2.83
1.41+2.24 1.41+4.12
0.00+3.61 1.00+4.47
B2
(d)
Figure 5: Example Trace of Theta*
6 Implementation Details and Optimization of your Code
Your implementation of A* should use a binary heap [4] to implement the open list. The reason for
using a binary heap is that it is often provided as part of standard libraries and, if not, it is easy
to implement. At the same time, it is also reasonably efficient in terms of processor cycles and
memory usage. You will get extra credit if you implement the binary heap from scratch, that is, if
your implementation does not use existing libraries to implement the binary heap or parts of it.
Do not use code written by others and test your implementations carefully. For example, make
sure that the search algorithms indeed find paths from the start vertex to the goal vertex or report
that such paths do not exist, make sure that they never expand vertices that they have already
expanded (GRAPH-SEARCH), and make sure that A* with consistent h-values finds shortest grid
paths. Use the provided traces to test your implementation.
Your implementations should be efficient in terms of processor cycles and memory usage. All
critical applications place limitations on the resources that search algorithms have available. Thus,
it is important that you think carefully about your implementations rather than use the given
pseudo-code blindly since it is not optimized. For example, make sure that your implementations
never iterate over all vertices except to initialize them once at the beginning of a search (to be
precise: at the beginning of only the first search in case you perform several searches in a row)
since your program might be used on large grids. Make sure that your implementation does not
determine membership in the closed list by iterating through all vertices in it.
Numerical precision is important since the g-values, h-values and f-values are floating point
values. An implementation of A* with the h-values from Equation 1 can achieve high numerical
precision by representing these values in the form m +
p
2n for integer values m and n. Nevertheless, your implementations of A* and Theta* can use 64-bit floating point values (“doubles”) for
simplicity, unless stated otherwise.
7 Questions and Deliverable
In this project you are asked to implement A* and Theta*, to run a series of experiments and report
your results and conclusions. You can work in groups of at most 3. Make sure to include the name
of every member of your group in both submissions. Only one member of the team should submit
the assignment. Please inform the TAs who are the members of your team by using the following
Google form: https://forms.gle/bqUWCeFWzR3fSn5N8.
Answer the following questions under the assumption that A* and Theta* are used on eightneighbor grids. Average all experimental results over the same 50 eight-neighbor grids of size
100 × 50 with 10 percent randomly blocked cells and randomly chosen start and goal vertices so
that there exists a path from the start vertex to the goal vertex. You need to generate these grids
yourself. To facilitate your experiments, save each grid into a file. Remember that we assumed
that paths can pass through vertices where diagonally touching blocked cells meet. All search
algorithms search from the start vertex to the goal vertex unidirectionally.
A grid is saved in a file using the following format. The first three lines contain two integers ( y)
each, specifying the start vertex, goal vertex, and the dimensions of the grid in terms of columns
×rows (the number of cells, not the number of vertices) respectively. Next, there are × y lines
each with three numbers: the x-coordinate, the y-coordinate and either 0 for a free cell or 1 for a
blocked cell. Your experiments have to be on grids of 100 × 50 but this format allows you to start
testing with smaller grids. Refer to figure 7 for a small example grid with its corresponding text
file.
(a) (b)
Figure 6: (a) Example grid of 4 × 3 with three blocked cells and start and goal vertices. (b)
Corresponding text file (line numbers shadowed), numbering starts from the upper left cell.
Different from our examples, A* and Theta* break ties among vertices with the same f-value in
favor of vertices with larger g-values and remaining ties in an identical way, for example randomly.
Hint: Priorities can be single numbers rather than pairs of numbers. For example, you can use
ƒ (s) − c × g(s) as priorities to break ties in favor of vertices with larger g-values, where c is a
s
start
sgoal
1 2 3 4 5
A
C
B
Figure 7: Example Search Problem
constant larger than the largest f-value of any generated vertex (for example, larger than the
longest path on the grid).
You are asked to submit part of your submission (questions a, b, c, d, e, f) by Feb. 7. The final submission of this assignment as well as followup homework questions below is due on Feb. 21.
Your submission must run and will be tested on ilab (https://resources.cs.rutgers.edu/
docs/instructional-lab/). You are free to use any programming language already available on
ilab. TAs will not upgrade or install anything. The TAs will evaluate your software by using different grid maps than yours, which follow the above format. Submit a compressed file containing
your source code as well as a README file with instructions on how to test your submission (i.e.
compilation, command to execute, etc).
You are asked to address the following questions:
a) Create an interface so as to create and visualize the 50 eight-neighbor grids you are going to
use for the experiments.
Your software should also be able to visualize: the start and the goal location, the path
computed by an A*-family algorithm. Visualize the values h, g and ƒ computed by A*-family
algorithms on each cell (e.g., after selecting with the mouse a specific cell, or after using the
keyboard to specify which cell’s information to display). Use the images in this report from
the traces of algorithms as a guide on how to design your visualization.
Highlight in your report your visualization, its capabilities and what implemented for it.
(10 points – due date: Feb. 7)
b) Read the chapter in your artificial intelligence textbook on uninformed and informed (heuristic) search and then read the project description again. Make sure that you understand A*,
Theta* and the Bresenham line-drawing algorithm. Manually compute and show a shortest
grid path and a shortest any-angle path for the example search problem from Figure 7. Manually compute and show traces of A* with the h-values from Equation 1 and Theta* with the
h-values h(s) = c(s, sgoal) for this example search problem, similar to Figures 3 and 5.
(5 points – due date: Feb 7)
c) Implement the A* algorithm for a given start and goal location for the grid environments.
Describe in your report what you had to implement in order to have the A* algorithm working.
(10 points – due date: Feb. 7)
d) Implement Theta*.
Describe in your report what you had to implement in order to have the Theta* algorithm
working.
(10 points – due date: Feb. 7)
e) Give a proof (= concise but rigorous argument) why A* with the h-values from Equation 1 is
guaranteed to find shortest grid paths.
(5 points – due date: Feb. 7)
f) Extra credit: Implement your own binary heap and use it in both algorithms. Discuss your
implementation in the final report. If you do execute this extra credit step, make sure that
any runtimes you report in your answers below how your own implementation of a binary
heap has influenced the running times.
Describe in your report what you had to implement for your own binary heap implementation.
(10 extra credit points – due date: Feb. 7)
g) Optimize your implementation of A* and Theta* relatively to what you submitted on Feb. 7.
Discuss your optimizations in your final report and show the difference in running times.
(10 points – due date: Feb. 21)
h) Compare A* with the h-values from Equation 1 and Theta* with the h-values h(s) = c(s, sgoal)
with respect to their runtimes and the resulting path lengths. In your final report show your
experimental results, explain them in detail (including your observations, detailed explanations of the observations and your overall conclusions) and discuss in detail whether it is fair
that A* and Theta* should use different h-values. If you think it is, explain why. If you think
it is not, explain why not, specify the h-values that you suggest both search algorithms use
instead and argue why these h-values are a good choice.
(10 points – due date: Feb. 21)
i) Identify cases where the paths found by Theta* with the h-values h(s) = c(s, sgoal) are longer
than the true minimal path in the continuous case. Report how much longer than the true
optimal paths are the Theta* paths and how much longer are the A* paths.
To this end, you can determine the true shortest paths with visibility graphs [5]. A visibility
graph contains the start vertex, goal vertex and the corner points of all blocked cells. Two
vertices of the visibility graph are connected via a straight line iff the straight line is unblocked. Figure 8, for example, shows the visibility graph for the example search problem
from Figure 1. A shortest path from the start vertex to the goal vertex on the visibility graph
is guaranteed to be the true shortest path in the continuous space. Show your experimental
results in your final report. You are not asked to necessarily implement the visibility graph
algorithm – although you already have all the necessary components available: the line of
sight check to define which pairs of vertices are visible and thus which edges exist on the
visibility graph, and then the A* algorithm for finding the shortest path on the visibility graph.
You can manually define the true shortest paths in the continuous space for the problems you
are experimentally evaluating.
s
start
sgoal
shortest path
1 2 3 4 5
A
C
B
Figure 8: Visibility Graph
(10 points – due date: Feb. 21)
(10 extra credit points for the implementation of the visibility graph – due date: Feb. 21)
j) A* with consistent h-values guarantees that the sequence of f-values of the expanded vertices
is monotonically non-decreasing. In other words, ƒ (s) ≤ ƒ (s
′
) if A* expands vertex s before
vertex s
′
. Theta* does not have this property. Construct an example search problem where
Theta* expands a vertex whose f-value is smaller than the f-value of a vertex that it has
already expanded. Do not forget to list the h-values of Theta* and argue that your h-values
are indeed consistent. Then, show a trace of Theta* for this example search problem, similar
to Figures 3 and 5.
(10 extra credit points – due date: Feb. 21)
Together with the final report you will have to submit a copy of your code.
Beyond Heuristic Search
30 points – all of these problems are due Feb. 21
Problem 2 – Adversarial Search: Consider the two-player game described in Figure 9.
a. Draw the complete game tree, using the following conventions: [3/4 points]
• Write each state as (sA, sB) where sA and sB denote the token locations.
• Put each terminal state in a square box and write its game value in a circle.
• Put loop states (states that already appear on the path to the root) in double square
boxes. Since it is not clear how to assign values to loop states, annotate each with a “?”
in a circle.
b. Now mark each node with its backed-up minimax value (also in circle). Explain how you
handled the “?” values and why. [3/4 points]
c. Explain why the standard minimax algorithm would fail on this game tree and briefly sketch
how you might fix it, drawing on your answer to (b). Does your modified algorithm give
optimal decisions for all games with loops? [3/4 points]
d. This 4-square game can be generalized to n squares for any n > 2. Prove that A wins if n is
even and loses if n is odd. [6/8 points]
Figure 9: The start position of a simple game. Player A moves first. The two players take turns
moving, and each player must move his token to an open adjacent space in either direction. If
the opponent occupies an adjacent space, than a player may jump over the opponent to the next
open space if any. (For example, if A is on 3 and B is on 2, then A may move back to 1.) The game
ends when one player reaches the opposite end of the board. If player A reaches space 4 first,
then the value of the game to A is +1; if player B reaches space 1 first, then the value of the game
to A is -1.
(10 points)
Problem 3 – Local Search: Simulated annealing is an extension of hill climbing, which uses
randomness to avoid getting stuck in local maxima and plateaux.
a) For what types of problems will hill climbing work better than simulated annealing? In other
words, when is the random part of simulated annealing not necessary?
b) For what types of problems will randomly guessing the state work just as well as simulated
annealing? In other words, when is the hill-climbing part of simulated annealing not necessary?
c) Reasoning from your answers to parts (b) and (c) above, for what types of problems is simulated annealing a useful technique? What assumptions about the shape of the value function
are implicit in the design of simulated annealing?
d) As defined in your textbook, simulated annealing returns the current state when the end of
the annealing schedule is reached and if the annealing schedule is slow enough. Given that
we know the value (measure of goodness) of each state we visit, is there anything smarter
we could do?
(e) Simulated annealing requires a very small amount of memory, just enough to store two
states: the current state and the proposed next state. Suppose we had enough memory to
hold two million states. Propose a modification to simulated annealing that makes productive
use of the additional memory. In particular, suggest something that will likely perform better
than just running simulated annealing a million times consecutively with random restarts.
[Note: There are multiple correct answers here.]
(10 points)
Figure 10: Sample Sudoku board
Problem 4 – Constraint Satisfaction Problem: Consider the
game Sudoku, where we try to fill a 9 × 9 grid of squares with
numbers subject to some constraints: every row must contain
all of the digits 1, . . . , 9, every column must contain all of the
digits 1, . . . , 9, and each of the 9 different 3 × 3 boxes must also
contain all of the digits 1, . . . , 9. In addition, some of the boxes
are filled with numbers already, indicating that the solution to
the problem must contain those assignments. Here is a sample
board:
Each game is guaranteed to have a single solution. That is,
there is only one assignment to the empty squares which satisfies all the constraints. For the purposes of this homework,
let’s use n,j to refer to the number in row , column j of the grid.
Also, assume that M of the numbers have been specified in the
starting problem, where M = 29 for the problem shown above.
a. This is an instance of a Constraint Satisfaction Problem. What is the set of variables, and
what is the domain of possible values for each? How do the constrains look like?
b. One way to approach the problem, is through an incremental formulation approach and apply
backtracking search. Formalize this problem using an incremental formulation. What are the
start state, successor function, goal test, and path cost function?
Which heuristic for backtracking search would you expect to work better for this problem, the
degree heuristic, or the minimum remaining values heuristic and why?
What is the branching factor, solution depth, and maximum depth of the search space? What
is the size of the state space?
c. What, is the difference between “easy” and “hard” Sudoku problems? [Hint: There are heuristics which for easy problems will allow to quickly walk right to the solution with almost no
backtracking.]
d. Another technique that might work well in solving the Sudoku game is local search. Please
design a local search algorithm that is likely to solve Sudoku quickly, and write it in pseudocode. You may want to look at the WalkSAT algorithm for inspiration. Do you think it will
work better or worse than the best incremental search algorithm on easy problems? On hard
problems? Why?
(10 points)
Problem 5 – Logic-based Reasoning: Consider the following sequence of statements, which
relate to Batman’s perception of Superman as a potential threat to humanity and his decision to
fight against him.
For Superman to be defeated, it has to be that he is facing an opponent alone and his opponent
is carrying Kryptonite. Acquiring Kryptonite, however, means that Batman has to coordinate with
Lex Luthor and acquire it from him. If, however, Batman coordinates with Lex Luthor, this upsets
Wonder Woman, who will intervene and fight on the side of Superman.
a. Convert the above statements into a knowledge base using the symbols of propositional logic.
b. Transform your knowledge base into 3-CNF.
c. Using your knowledge base, prove that Batman cannot defeat Superman through an application of the resolution inference rule (this is the required methodology for the proof).
(5 points)
References
[1] S. Koenig, K. Daniel, and A. Nash, “A project on any-angle path planning for computer games
for ’introdction to artificial intelligence’ classes,” Department of Computer Science, University
of Southern California, Los Angeles, Tech. Rep., 2008.
[2] A. Nash, K. Daniel, S. Koenig, and A. Felner, “Theta*: Any-angle path planning on grids,” in
Proc. of the AAAI Conf. on Artificial Intelligence (AAAI), 2007, pp. 1177–1183.
[3] Bresenham, “Algorithm for computer control of a digital plotter,” IBM Systems Journal, vol. 4,
no. 1, pp. 25–30, 1965.
[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press,
September 2009, third Edition.
[5] M. De Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry:
Algorithms and Applications, 2nd ed. Springer, 1998.
