Exam 1 Review

CSCI 455 Spring 2008

Exam Logistics

• Take Home Exam. 
• Review on Feb. 25 in class. Due Mar 1 at beginning of class.
• Must record starting and ending times, expect to take about 1 1/2 hours.
• Be honest, but do not exceed time limit.
• Open book, but closed internet, closed neighbor.
• Mix of true/false, short answer, matching, and "solve the following" problems.

Topics

Framework for Decision-Making

• States, actions, consequences, goals, preferences, and utilities.
  • Definitions
  • Diagrams
    
• PEAS decomposition
• Environment description
  • Fully/Partially observable
  • Deterministic/stochastic
  • Episodic/sequential
  • Static/dynamic
  • Discrete/continuous
  • Single agent/Multiple Agent
• Rationality, optimization, intelligence

Potential Fields

• Definition of a behavior
• Representing behaviors with fields: concepts and mathematical encoding
  • Attractive
  • Repelling
  • Tangential
  • Uniform
  • Random
  • Perpendicular
• Combining behaviors by combining potential fields
• Choosing actions
• Internal states with potential fields
  • Avoid the past (from reading)
    

Search

• Nodes, states, goals
• Search strategy: definition
• Uninformed search strategies: algorithms, completeness, optimality, time complexity, space complexity
  • Breadth-First Search
  • Depth-First Search
  • Uniform-Cost Search
  • Depth-Limited Search (from your reading)
  • Iterative Depening (from your reading)
  • Bi-directional search (from your reading)
• Three techniques for avoiding repeated states
• Informed search strategies: algorithms, completeness, optimality, time complexity, space complexity
  • Greedy Search
  • A*
• Cost-to-arrive, cost-to-go, heuristics, admissible heuristics, consistent heuristics
  
• Optimal efficiency
• Graph versus tree implementations of search
  
• Lessons from search lab
• Interrelationships between search types
• Online versus offline searches
• Goal-finding
  • hill-climbing
  • random restart
    
  • beam search
  • gradient descent (continuous spaces)
    

Probability Theory

• Axioms of probability
  
• Random variables
  • functions
  • measurable
  • derived distributions
    
• Probability mass functions and probability density functions
• Conditional probabilities and independence
  
• Bayes rule
  • Prior
  • Posterior
  • Likelihood
  • Information-gathering process
  • Examples
  • Combining Evidence: sequential Bayes
• Gaussian distributions
• Bayes Filter

What's Not On the Test

• Lejos API: You're writing programs already
• Localization, Chapter 7:  It's a lot of math, and we're taking it slow