Description

CS1504 — Artificial Intelligence
Session — 03

• You can upload only one ZIP file
• The naming convention is “<Your first name (first letter capital and all the other letters small)>CS1504-S02.zip”

(a) How do we formulate the state-space? How many states are there? How many paths are there to the goal? Think carefully to define a good state-space. Justify your decisions.
(b) How do we define the actions in your formulation of the state-space?
(c) Formulate this problem in Python by subclassing the Problem class in “search.py” of the reference implementation. Take extra care to implement ACTIONS to find successor states of a given state.
(d) Define your evaluation function to evaluate the goodness or badness of a state using an admissible (and, preferable consistent as well) heuristics function (it should be easy to find a heuristics for this problem!)
(e) Create several instances (at least 100) of this problem by randomly generating planes with random start and goal points and random polygons as obstacles.
(f) Solve all the instances using the following search strategies:
• Any basic strategy of your choice (DFS/BFS/IDS)
• Best-first greedy search
• A∗ search
(g) Perform an empirical analysis in terms of number of nodes generated, expanded, actual time taken, completeness, optimality, etc. Which algorithm performs better, in general, on all the instances?
Page 2