Homework Set #1
Agents and Search
1) Go
to http://www.aaai.org/AITopics/index.html,
and familiarize yourself with the Topics page that is maintained by AAAI. Choose one of the topics from the pull down
menu (choose an area in AI that interests you most) and explore the articles,
web sites, current news, research, etc. that are linked from the AAAI
site.
In 1-2 type-written pages, describe the area
that you chose. Include the answers to
the following questions (when applicable):
a) Why
is this area part of the study of Artificial Intelligence?
b) What
are the challenges of the research in this area for AI scientists?
c) What
are the some of deployed current systems that use AI technology in this area?
2) State
Space formulation:
The sliding tile puzzle has some number of black
tiles followed by a space followed by some number of white tiles.
The
goal is to have all black tiles to the right of all white tiles. We do not care
where the blank spot is.
You can represent the puzzle as a
list, where B represents a black tile, W represents a white tile, and O
represents the blank.
The example above would be: (B B O W W W)
There
are two legal moves for this puzzle:
i)
A tile may move to the adjacent location (left or
right) if that location is blank. This move has a cost of 1.
ii) A
tile can jump over one or two other tiles into the blank location. The cost of this move is the number of tiles
that were jumped over.
a) Give
a formulation for this problem in terms of our discussion in class. Include the definition of:
i)
state
ii) start
state
iii) goal
state
iv) successor
function
b) Show
the search tree for the configuration (B
O W W) for both depth first and breadth first
without taking costs into account, so that you can arrive at a solution to the
problem. Describe for the more
complicated pictured example above what you would do to arrive at the shortest
path (with costs taken into account).
c) Extra
credit: Implement breadth first search and depth first search so that you can
input an initial configuration, and output the path that will lead to the goal
state.
3) Given
the choice of the following search strategies:
a) Breadth-first
search
b) Depth-first
search
c) Best-first
search
d) Hill
Climbing
e) Constraint
Propagation
Explain which one you would use
(and why) for the following problems:
a) 8-puzzle
b) 8
queens problem
c) Math
theorem proving
d) Machine
design
e) Traveling
Salesman Problem
f)
Class scheduling problem
4) Problems
from AIMA:
Chapter 2: 2.5
Chapter 3: 3.1, 3.6, 3.7a,d
3.17
Chapter 4: 4.2, 4.5 (requires reading pages 95-96)