Artificial Intelligence Midterm 1 Review

Please bring a calculator. Notes will not be allowed.

Topics you should know:

  • Breadth-first search, Uniform cost search, A* search
    • Know how to implement these algorithms.
    • Know how they differ.
    • Know how they can be applied with various nuances of problems.
    • Know what a heuristic is, and what is an admissable heuristic for A* search.
  • Utility theory
    • Marginalizing away probability.
    • Choosing the best utility.
    • How to break down a problem into a decision tree.
    • How to calculate utilities with complex scenarios.
  • Genetic algorithms
    • Know what it does and how it works.
    • Know how to implement common operations.
    • Know its strengths and weaknesses.
    • Be able to give pseudo-code if needed.
  • A few other optimization techniques (Hill Climbing, Simulated Annealing, Particle Swarm Optimization, Ant Colony Optimization)
    • Just a very high-level understanding will be sufficient.

Example questions:

  • Suppose you want your robot to achieve some goal. Also, suppose you have an optimal plan to arrive at that goal. How can you determine what is the best action to perform right now?
  • Is breadth-first search optimal (with respect to efficiency of finding the solution) if the cost function is consistent?
  • Is uniform cost search optimal (with respect to path cost) if the cost function is inconsistent?
  • Is uniform cost search optimal in any way if the heuristic is inadmissable? (hint: trick question, uniform cost search uses no heuristic.)
  • What is the role of the priority queue in uniform cost search? What would happen if you sorted this queue incorrectly?
  • How would it affect the computational complexity of uniform-cost search if you fail to dectect states that were previously visited?
  • Describe how you might implement uniform cost search for a continuous search space. Would the solution still be optimal? Why or why not?
  • What conditions are necessary for A* search to find an optimal solution?
  • Please give an example of an inadmissable heuristic for A* search.
  • Describe a problem for which uniform cost search would be impractical.
  • Give an example of a problem that might require you to plan in a high-dimensional space.
  • Describe how you might build an intelligent agent to control a robotic vacuum.
  • What is determinism? Are robots determinisitic? What would it mean if humans were?