ANP- Project Solved

•   Make sure to name the submitted file ID1-ID2.zip (or .pdf) with ID1,ID2 - the students’ ids.

•   For hands-on parts, your source code should be submitted as well (include it in the above zip file).

Theoretical questions:

1.    (Graph search) Consider the graph G = (V,E) shown in Figure 1. Find the shortest path between the denoted start and goal nodes using the following algorithms. In each case, provide a detailed explanation of the algorithm run, and state the order in which states are expanded.

(a)    Breadth-first search (BFS) algorithm, considering unweighted edges, as in Figure 1(left).

(b)    Depth-first search (DFS) algorithm, considering unweighted edges, as in Figure 1(left).

(c)     Best-first search (Dijkstra) algorithm, considering weighted edges, as in Figure 1(right).

(d)    A* algorithm, considering weighted edges and the heuristic function h, as in Figure 1(right).

(e)    Is A* more efficient than Dijkstra in the considered setting? Explain your answer.

 

Figure 1

2.    (A∗) In this question we focus on the properties of heuristic functions. Reminder:

•   A heuristic function is admissible if h(xi) ≤ dist(xi,xτ) for every node xi with coordinates xi in graph G, where dist(xi,xτ) is the shortest distance from xi to xτ.

•   A heuristic function is consistent if

–    h(xτ) = 0 for the goal node τ with coordinates xτ.

1

–    h(xi) ≤ c(xi,xj) + h(xj) for every node i with coordinates xi and its children j with coordinates xj.

               • A heuristic function is −consistent, with       1, if

–    h(xτ) = 0 for the goal node τ with coordinates xτ.

–     ) for every node i with coordinates xi and its children j with coordinates xj.

(b)    Prove that if h(1) and h(2) are consistent heuristics, then h =. max(h(1),h(2)) is also consistent.

(c)     Prove that if h(1) and h(2) are consistent heuristics, then consistent.

(d)    Provide an example of an admissible heuristic h that is not consistent. Show explicitly why h does not satisfy the consistency property.

Hands-on tasks:

1.    (Probabilistic Roadmap) Consider a 2D environment of size N ×N and a known set Cobs of scattered obstacles. For simplicity, consider all obstacles are represented by rectangular polygons of size  aligned with x and y axes (i.e. not rotated).

(a)    Implement on your own a function GeneratePRM which creates a simplified 2D probabilistic roadmap (PRM) G = (V,E). In this simplified version, consider any two (sampled) points v1 and v2 in the 2D space can be connected by a straight line if the Euclidean distance dist(v1,v2) between them is less than a distance threshold thd, and the path from v1 to v2 does not intersect with an obstacle (i.e. in Cfree). Assign the weight of the corresponding edge (v1,v2) to be dist(v1,v2). Assume sampling of new candidate positions is done from a uniform distribution

•   Input: distance threshold thd, number of nodes Nnodes, set of obstacles Cobs.

•   Output: a PRM G = (V,E).

(b)    Let N = 100. Randomly scatter nobs = 15 identical obstacles in the 2D environment, with              = 15 and

 = 10. Given this environment (in terms of obstacles), draw on separate plots the obstacles and the corresponding probabilistic maps considering all permutations Nnodes ∈{100,500} and thd ∈{20,50}. For each configuration, indicate in the plot the number of edges and an average node degree in the constructed

PRM G.

2.    (Graph search) Consider the generated environment and the constructed PRM with Nnodes = 100 and thd = 50 from clause 1b. Consider start and goal positions to be, respectively, at the bottom left and top right corners of the 2D N × N considered environment. For simplicity, denote by xstart and xgoal the closest nodes in G to these positions. Implement on your own the Dijkstra algorithm, or/and an A* with Euclidean distance heuristic, and use it to find the shortest path from xstart to xgoal. Plot the corresponding shortest path on top of the PRM, while indicating the obstacles.