MP practicalities

Questions related to what you built in MP 10 and 11.

Planning

• Historical figures and algorithms
  • STRIPS planner
  • Roger Schank
• Representing a planning problem
  • State and action representation
  • Preconditions and effects (postconditions)
• Approaches to planning
  • Sussman anomaly
  • Situation space planning vs. plan space planning
• Partial order (plan space) planning:
  • the idea
  • plan modification operations
  • plan defects (open preconditions, threats) and how to fix them
• Representations of objects and actions
  • object types and instances
  • count vs. mass nouns
  • fluents
  • activities, state changes, accomplishments
  • decaying properties and maintenance actions
• Upgrades to the environment
  • Incompletely known
  • Other actors, moving obstacles
  • Actions might not execute as planned
  • Time limitations on planning
  • Contingent planning
• Algorithms and planning languages
  • Truth maintenance systems
  • Towers of Hanoi takes time exponential in input size (number of rings)
  • SATplan
  • GraphPlan

Game Search

• Game tree
• What is ..
  • a "ply"? a "move"?
  • a Zero-sum game
  • a stochastic game?
  • a fully observable game?
• What other game features could make planning hard? (E.g. dynamic world, more than two players, limits on thinking time.)
• Basic method
  • Minimax strategy
  • Minimax search (using depth-first search)
  • Depth cutoff
  • Heuristic state evaluation
• Alpha-beta pruning
  • How it works
  • How well it works
  • Impact of move ordering
  • You will not have to write out detailed code for alpha-beta search. Concentrate on understanding what branches it prunes and why.
• Optimizations around depth cutoff
  • Horizon effect
  • Quiescence search
  • Singular extension
  • Early pruning
• Other optimizations
  • Memoization (transposition table)
  • Opening moves, endgames
  • Where might we use a neural net to help out?
• Interesting recent algorithms
  • Libratus
  • AlphaZero
• Monte Carlo tree search

Bayes nets

• Required structure (e.g. it's a DAG, probability table at each node)
• How does the geometry (i.e. nodes, edges) of a bayes net relate to conditional independence of the probabilities it represents?
• What do local node connections imply about independence? conditional indepedence?
  • Explaining away
• Comparing size of model to full joint probability table
• Reconstructing the joint distribution from a Bayes net
• Building a Bayes net from a joint probability distribution
  • How is this affected by the order in which we choose variables?
• Topological sort of a partial order
• Inference, aka calculating specific probability values using the geometry and tables in a Bayes net (very simple examples only)
• Efficiency results for inference
  • Efficient for polytrees (and what is a polytree?)
  • Some other geometries can be solved efficiently via junction tree algorithm
  • NP complete (aka probably exponential) in general case