AI-638 2007 Assignments                   Animations on a common graphical interface.

 

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.

 

 

  1. Best 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.

 

  1. A* (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.

 

  1. IDA* (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.

 

  1. RBFS (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

 

  1. DCFS (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.

 

  1. SMGS (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.

 

  1. BFHS (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 orange.

 

  1. 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.

 

  1. 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.

 

  1. ACO 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. 

 

  1. TSP (3) User chooses number of cities.

 

    1. Start with greedy construction of a tour,
    2. 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”.
    3. 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.

 

  1. AO* (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. 

 

  1. 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*.

 

  1. A cross word generator (2). Takes as input a crossword grid, that the user can edit, a library of words, and generates a cross word.

 

  1. Goal 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.

 

  1. A* Planning (3). Accept a planning domain, and a planning problem, and implement A* search. Use a domain independent heuristic function.

 

  1. Any specific application development in consultation with the Instructor and the TAs.