*** AI map

title

Chapter 1: Introduction

• the importance of AI
• what is AI
• the different approached to AI

Chapter 2: Intelligent Agents

• definition of an agent
• the structure of agents
• learning agents

---

Lecture 2: Agents and Search

• options to design an AI agent
• designing rational agents
  • reflex agent
  • planning agent
• search problems
• state space
• state space graph vs search tree
  • state space graph
  • search tree
• search algorithm
  • tree search algorithm
  • depth-first search - dfs
  • breadth-first search - bfs
  • iterative deepening
  • cost-sensitive search
  • uniform cost search - ucs

Lecture 3: Informed Search

• search so far
  • search problems
  • search tree
  • search algorithm
• pancake problem
• fringe strategy - the one queue
• uniform cost search - ucs
• search heuristics
• greedy search
• a* search
  • Optimality of A* Tree Search
  • properties of A*
  • A* applications
  • tree search, graph search notices
  • consistency of heuristics
  • optimality of A* graph search & summary
• admissible heuristics & creating admissible heuristics
  • example: 8 Puzzle I, II, III
• UCS vs A* Contours
• semi lattice of heuristics
  • trivial heuristics, dominance
• search models & search gone wrong

---

Search Heuristics5

• Heuristic Function: Estimates how close a state is to a goal, designed for specific search problems.
• Examples: Manhattan distance, Euclidean distance for pathing.

Greedy Search

• Strategy: Expands the node that appears closest to a goal state based on a heuristic estimate6.

A* Search

• Combining UCS and Greedy: Orders by the sum of backward cost ( g(n) ) and forward cost ( h(n) ).
• Optimality of A Tree Search*: Assumes admissible heuristics and claims that optimal goals will exit the fringe first.
• Properties of A*: Expands mainly toward the goal while ensuring optimality7.
• A Applications*: Used in various fields like video games, routing problems, and language analysis.
• Tree Search and Graph Search Notices: Importance of detecting repeated states and implementing a closed set.
• Consistency of Heuristics: Ensures estimated heuristic costs are less than or equal to actual costs.
• Optimality of A Graph Search & Summary: A is optimal with admissible/consistent heuristics, and heuristic design is crucial8.

Admissible Heuristics & Creating Admissible Heuristics9

• Admissibility: Heuristics must be optimistic and never outweigh true costs.
• Example - 8 Puzzle: Different heuristics like the number of tiles misplaced and total Manhattan distance.

UCS vs A* Contours10

• Comparison: UCS expands equally in all directions, while A* focuses mainly toward the goal.

Semi Lattice of Heuristics11

• Trivial Heuristics and Dominance: The concept of dominance and the semi-lattice structure of heuristics12.

Search Models & Search Gone Wrong

• Search and Models: The effectiveness of search is dependent on the accuracy of the world models.
• Search Gone Wrong: Issues that arise when models do not accurately represent the real world.