AI-638 2007 Assignments Animations on a common graphical
Platform - Generate and display large dense (planar) graphs. Non uniform
distribution (parameter controlled). Label arcs with actual costs
(Euclidean distance + small random value). Functions to colour/highlight arcs
and nodes. MoveGen function (returns list of neighbours). Function to display
h(n) (dashed colored line from node to goal). Options to read in graphs from a
file (in some format), and control the speed of a demo.
First Search and HC (2). Show current node in red. Add children to OPEN in
blue. CLOSED nodes in orange. Show dashed lines from nodes on OPEN to the goal
node. Highlight the closest node with blue line. In case of HC, show current
node in red. Nodes visited earlier in yellow. Neighbours of current in blue.
Show heuristic arcs from blue nodes to goal and highlight the closest.
(2). Show OPEN nodes in blue and CLOSED in orange. Show selected node as red,
show propagation of g-values. Work on large UNEVEN graphs. User selects start
and goal, and can control demo speed, stepping through etc.
(2). Let the bound on f-values be U. Draw an oval with this (for any point O
on the oval d(S,O) + d(O,G) = U). Show how IDA* does DFS within these bounds.
User should be able to select start and goal nodes, be able to decide on step
increment size for f-values, and control the pace of animation. Show nodes
visited in earlier rounds in yellow. Overwrite current CLOSED nodes in orange,
and OPEN nodes in blue.
(2). On a semi-dense non uniform graph, user selects start and goal state.
Show path to current node and the OPEN nodes in light blue, and best node in
blue. Show the second best node in red. Show rolled back nodes in orange
(3). Show the deleted CLOSED list in yellow, and the OPEN in blue. Show the
active arcs of nodes in OPEN in blue as well (or the successor nodes in light
blue). Show the relay nodes in red. Recursively show the path reconstruction.
(3). Assume a memory size of K nodes. On a dense graph show the progress of
SMGS. Show deleted kernel in yellow. The relay layers in red. The boundary in
orange and the OPEN nodes in blue. Show the sparse path when goal is found,
and recursively fill in the dense path.
(2). Estimate upper bound U on solution by some means (beam search or k*h(S)
for some k). Draw an oval with this (for any point O on the oval d(S,O) +
d(O,G) = U). Demo BFHS as a BFS within these bounds. OPEN in blue, closed in
BeamstackSearch (3). Show Beam on the frontier in blue, the CLOSED in light
blue. Show nodes that have been backtracked over in orange. Show beamstack on
the side in matching colors (frontier blue, closed light blue). User should be
able to select beam width and pace of animation.
DCBeamStackS (4). (combination of SMGS, DCFS, BSS) User should be able to
select beam width. Show the four layers of width w. Show deleted nodes in
yellow. Boundary in orange, open in blue and relay nodes in red. Show
backtracking as regeneration. Show beamstack on the side as a vertical bar.
for TSP (2). User chooses number of cities, connectivity, number of ants, and
evaporation rate (provide default values). Choose a color scale for displaying
strength of pheromone (say light yellow to orange to red). Display the arcs in
color depending upon pheromone level. Optionally animate the ant movement.
(3) User chooses number of cities.
Start with greedy construction of a tour,
followed by hill climbing and simulated annealing. Show the previous tours
in yellow, and current tour in blue. User to be able to adjust speed of
demo. Show the temperature on a vertical “thermometer”.
For the GA option construct initial population (a) randomly (b) greedy
construction starting at different locations. Allow user to select mutation
rate. Display as in SA, but also display average population density. In all
methods (optionally) display a plot of (decreasing) tour cost with time.
(2) Randomly generated AO graphs with “actual” arc costs as random additions
to Euclidean distances. Heuristic estimates constructed in a bottom up manner
as sum of distances. Show the graph generated in orange. Show the traversal
down the marked path, and expansion of a node. Show the values being backed up
and path marked.
Games (2) Alpha-Beta and SSS*. Randomly generated dense game trees (allow user
to select branching factor and depth. Compress entire tree to fit on screen
(choose node size to draw dynamically). Show tree generated by Alpha-Beta in
orange. Overwrite with a tree in blue by SSS*.
cross word generator (2). Takes as input a crossword grid, that the user can
edit, a library of words, and generates a cross word.
Stack Planning (2). Accept a planning domain and a planning problem, and
illustrate GSP. Show the top few elements in a stack, show what happens when
something is popped (goes into plan, or is replaced by action and
precondition). Show the planning being constructed.
Planning (3). Accept a planning domain, and a planning problem, and implement
A* search. Use a domain independent heuristic function.
specific application development in consultation with the Instructor and the