Skip to content

Latest commit

 

History

History
98 lines (94 loc) · 3.53 KB

1.Intro.md

File metadata and controls

98 lines (94 loc) · 3.53 KB

Introduction

Outline

  • Introduction to AI and (AI) Planning
  • Classical Planning as Heuristic Search and Width-Based Search
  • Beyond Classical Planning
    • Factored-Model-Free
    • Non Determinism
    • Uncertainty
    • Soft goals
    • Plan Recognition
    • Epistemic (social) Planning
  • Reinforcement Learning: Learning through Experience
  • Multi agent Planning
  • Hot/Latest exciting discussions on AI Ethics

Prerequisite

  • Algo (DP)
  • Set Theory
  • Propositional Logic
  • Probabilistic Theory

Complexity

  • P
    • can be solved in polynomial time by a deterministic machine
  • NP
    • can be verified in polynomial time by a deterministic machine
    • can be solved (guessed) in polynomial time by a non-deterministic Turing machine
  • NP-hard
    • which all NPs can be reduced to
    • might not be NP
    • at least as hard as NP
  • NP-complete
    • in both NP and NP-hard
  • P=NP?
    • whether polynomial time algorithms actually exist for solving NP-complete
    • If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss ... —— Scott Aaronson, MIT

AI

  • automation of intelligent behavior
    • make rational action choices
  • Rational agents
    • Agents
      • do what
        • sensors -(perceive environment)-> percepts
        • actuators -(act upon environment)-> actions
      • examples
        • humans
        • animals
        • robots
        • software agents (softbots)
    • best case (‘the right thing’) is often unattainable
      • Rationality vs. Omniscience
      • Performance measure × Percepts × Knowledge → Action
  • what do AI do
    • Humanly vs Rationally
    • Thinking vs Acting
  • Solver
    • general
    • deals with any problem expressed as an instance of model (families of problems)
      • Linear Equations Model
        • tractable
  • AI solver
    • intractable
    • tasks
      • SAT/SATISFIABILITY/Boolean satisfiability problem/Propositional Satisfiability Problem
        • find state that satisfies constraints
        • NP-Complete
          • worst-case exponential in number of variables
        • --(generalized with non-boolean, non-clause constraints)--> CSPs(Constraint satisfaction problem)
        • key
          • efficient inference (poly-time)
            • unit resolution
            • conflict-based learning
      • Planning Problems
        • find action sequence that produces desired state
      • Planning with Feedback
        • find strategy for producing desired state
    • challenge
      • scalability
        • need to recognize and exploit the problems
          • lots of ideas
            • effective inference methods
              • derivation of h
              • conflict-learning
            • islands of tractability
              • treewidth methods and relaxations
            • transformations
              • compiling away incomplete info
              • extended goals
          • but methodology empirical
            • benchmarks
            • competitions
  • Planning
    • model-based
    • NP-hard
    • planner
    • classical planning & ai planing