# Artificial Intelligence Foundations — MASTER ## The mental model that makes classical AI finally click Artificial Intelligence can look like a giant collection of unrelated subjects: * search * logic * probability * planning * Bayesian networks * MDPs * POMDPs * utility * inference But they are actually different answers to one question: > **Given what I know about the world, what should I do next?** That is AI. An AI system observes something, builds or updates some representation of the world, reasons about what might be true, predicts what might happen, compares possible actions, and chooses one. A useful high-level picture is: ```text THE WORLD │ ▼ Observations │ ▼ ┌───────────────┐ │ AGENT │ │ │ │ What is true?│ ← inference │ What may │ ← uncertainty / probability │ happen? │ │ What can I │ ← search / planning │ do? │ │ What do I │ ← utility / decision theory │ prefer? │ └───────┬───────┘ │ ▼ Action │ ▼ THE WORLD ``` Almost everything in this chapter fits somewhere inside that loop. * * * # 1\. Intelligent Agents Start here, because the **agent** is the central abstraction of AI. An intelligent agent is something that: 1. observes its environment, 2. reasons about the situation, 3. chooses an action, 4. acts, 5. receives new observations, 6. repeats. Formally: ```text Environment → Perception → Agent → Action → Environment ``` Examples: * a chess engine observes a board and chooses a move, * a robot observes camera/LiDAR data and chooses motion commands, * a recommendation system observes user behavior and chooses recommendations, * an LLM agent observes conversation/tool results and chooses its next message or tool call, * an autonomous car observes the road and chooses steering, acceleration, or braking. The key word is **action**. A system that merely recognizes cats is a model. A system that recognizes a pedestrian and decides to brake is behaving as an agent. * * * ## Rational agents Classical AI often talks about a **rational agent**. Rational does not mean: > always makes the objectively perfect decision. It means: > chooses the action expected to produce the best outcome given the information currently available. Suppose a robot reaches a corridor. It believes: ```text Left path: 80% chance of reaching destination in 2 minutes 20% chance blocked Right path: 100% chance of reaching destination in 5 minutes ``` There is no universally correct decision. The answer depends on what the robot values: * speed, * reliability, * energy, * safety, * risk. Therefore intelligent behavior requires not only knowledge. It requires **preferences**. We will later represent those preferences using **utility**. * * * # 2\. The Agent's World Before designing an AI system, ask what kind of environment it operates in. Several distinctions matter enormously. ## Fully observable vs partially observable ### Fully observable The agent knows the complete relevant state. Example: ```text Chess board ``` Every piece and position is visible. ### Partially observable Some state is hidden. Example: ```text Autonomous robot ``` A wall may hide a pedestrian. Sensors may be noisy. The robot therefore cannot say: ```text The pedestrian definitely isn't there. ``` Instead: ```text I currently believe there is a 12% probability that something is behind the obstruction. ``` Partial observability leads naturally toward: * probability, * belief states, * Bayesian reasoning, * POMDPs. * * * ## Deterministic vs stochastic A deterministic environment behaves predictably. ```text action + state → exactly one next state ``` For example: ```text 5 + 3 → 8 ``` A stochastic environment contains randomness or uncertainty. ```text action + state → distribution over possible next states ``` Example: A robot drives forward on slippery terrain. ```text 90% → moves forward correctly 7% → slips left 3% → slips right ``` This difference eventually separates ordinary planning from MDP-style decision making. * * * # 3\. Search Imagine that you know: ```text current state goal state possible actions ``` but you do not immediately know which sequence of actions reaches the goal. Then you have a **search problem**. Example: ```text Current location: Kathmandu Goal: Pokhara Possible roads: ... ``` Or: ```text Current chess board Goal: checkmate Possible actions: legal moves ``` Or: ```text Robot at room A Goal: room D Possible actions: move through connected doors ``` Search explores possible futures. * * * # 4\. State Spaces Search becomes much easier to understand if you imagine a giant graph. Every possible situation is a **state**. Every possible action creates an edge to another state. Example: ```text A / \ B C / \ \ D E F \ G ``` Suppose: ```text Start = A Goal = G ``` The search algorithm explores this graph until it finds a path. ```text A → C → F → G ``` This entire graph is called the **state space**. Real AI problems can have unbelievably large state spaces. Chess has roughly: ```text 10^40 possible legal positions ``` So simply exploring everything is impossible. This brings us to one of the most important ideas in AI: > **Intelligence often means searching less intelligently rather than searching everything blindly.** * * * # 5\. Uninformed Search An uninformed search algorithm knows: ```text where it is what actions exist whether it reached the goal ``` but has no special estimate of which direction looks promising. Two classic algorithms matter. * * * ## Breadth-First Search — BFS BFS explores shallow states first. ```text Start Level 0: A Level 1: B C Level 2: D E F Level 3: G ``` It searches outward like expanding circles. Useful property: > If every action has equal cost, BFS finds the shortest path. Problem: It may consume huge amounts of memory. * * * ## Depth-First Search — DFS DFS chooses one route and keeps going. ```text A ↓ B ↓ D ↓ ... ``` If it reaches a dead end, it backtracks. Memory use is smaller, but it can waste enormous amounts of time going deeply down bad paths. * * * # 6\. Cost-Based Search Sometimes actions have different costs. Example: ```text Road A → 10 km Road B → 40 km ``` Then shortest number of actions is not necessarily cheapest. We define: ```text g(n) = cost from start to node n ``` **Uniform Cost Search** always expands the state with the lowest known `g(n)`. That gives us the cheapest route when costs are non-negative. But it still does not know where the goal is. For that we introduce heuristics. * * * # 7\. Heuristic Search A **heuristic** is an educated estimate of how promising a state is. Usually: ```text h(n) = estimated cost from state n to the goal ``` Imagine navigating a map. You know: ```text g(n) = road distance already travelled h(n) = straight-line distance remaining ``` The heuristic does not need to know the exact future. It merely provides useful direction. * * * ## Greedy Best-First Search Greedy search chooses the state with smallest: ```text h(n) ``` Meaning: > Go toward whatever currently looks closest to the goal. This can be extremely fast. But it can also be fooled. Suppose a mountain sits between you and your destination. Straight-line distance says: ```text Go directly toward the destination. ``` Reality says: ```text There is no road through the mountain. ``` A heuristic is guidance, not truth. * * * # 8\. A\* Search A\* combines: ```text how expensive the journey has already been ``` with: ```text how expensive we estimate the remainder will be ``` The famous equation is: ```text f(n) = g(n) + h(n) ``` where: ```text g(n) = actual cost so far h(n) = estimated remaining cost f(n) = estimated total journey cost ``` This equation is worth remembering permanently. Think: ```text PAST + FUTURE ESTIMATE ``` A\* balances them. * * * ## Why A\* is such a beautiful algorithm Suppose two routes exist. Route A: ```text cost already spent = 100 estimated remaining = 5 f = 105 ``` Route B: ```text cost already spent = 20 estimated remaining = 40 f = 60 ``` Greedy search sees: ```text 5 < 40 ``` and prefers A. A\* sees the full estimated journey: ```text 105 > 60 ``` and prefers B. That is much more sensible. * * * # 9\. Good Heuristics A heuristic is often called **admissible** if it never overestimates the true remaining cost. ```text h(n) ≤ true remaining cost ``` Why is that useful? Because A\* can then guarantee an optimal solution under standard conditions. Straight-line distance on a road map is a classic example. Actual road distance cannot normally be shorter than the straight line between two locations. * * * # 10\. Search Is Everywhere Do not think search means only "search engines." AI search means: > exploring possible states, hypotheses, actions, configurations, or futures. Examples include: ```text Route planning Chess Robot navigation Game playing Scheduling Code synthesis Theorem proving Puzzle solving Planning Drug design Architecture optimization LLM reasoning ``` Even many modern AI systems quietly contain search. Beam search in language generation? Search. Tree search in AlphaZero? Search. Agent trying several possible plans? Search. * * * # 11\. Constraint Satisfaction Problems Some problems are not naturally: ```text find a path through states ``` Instead they are: ```text assign values to variables while satisfying rules ``` These are **Constraint Satisfaction Problems**, or CSPs. A CSP consists of: ```text Variables Domains Constraints ``` Example: Schedule three classes. Variables: ```text Math Physics AI ``` Domains: ```text {9 AM, 10 AM, 11 AM} ``` Constraint: ```text Math ≠ Physics ``` if they use the same classroom. Another: ```text AI ≠ Math ``` if the same professor teaches both. The job is to find assignments satisfying all constraints. * * * ## Sudoku is a CSP Variables: ```text each empty cell ``` Domain: ```text 1...9 ``` Constraints: ```text no duplicate number in row no duplicate number in column no duplicate number in 3×3 block ``` You are not really navigating. You are satisfying constraints. * * * # 12\. Constraint Propagation A powerful CSP idea is: > Once you learn something, use it immediately to eliminate impossible possibilities elsewhere. Suppose: ```text A ∈ {1,2,3} B ∈ {1,2,3} Constraint: A < B ``` If we discover: ```text A = 3 ``` then there is no valid value for B. We can reject that branch immediately. This is called **constraint propagation**. Instead of blindly searching everything, knowledge shrinks the search space. This principle appears all across AI: > **Reasoning is often search-space reduction.** * * * # 13\. Knowledge Representation An intelligent system must represent what it knows. That sounds simple. It is not. Consider: ```text A dog is in the room. ``` How should an AI store this? Maybe: ```text Dog(d1) Inside(d1, room1) ``` Now: ```text Every dog is an animal. ``` could become: ```text Dog(x) → Animal(x) ``` Then the AI can infer: ```text Animal(d1) ``` This is **knowledge representation**. It asks: > How do we encode facts, objects, relationships, rules, categories, events, time, causation, uncertainty, and meaning so that a machine can reason about them? * * * # 14\. Different Forms of Knowledge Knowledge is not all the same. Consider: ### Facts ```text Paris is in France. ``` ### Rules ```text If X is a mammal, X is warm-blooded. ``` ### Relationships ```text Alice is Bob's manager. ``` ### Procedures ```text To make tea: boil water → add tea → steep ``` ### Probabilistic knowledge ```text Rain makes wet roads more likely. ``` ### Temporal knowledge ```text Event A happened before Event B. ``` ### Causal knowledge ```text Pressing this switch causes the motor to stop. ``` Good AI architectures often require several representations simultaneously. * * * # 15\. Logic Logic gives us rules for determining what conclusions follow from what premises. Example: ```text All robots with empty batteries cannot move. Robot R has an empty battery. ``` Therefore: ```text Robot R cannot move. ``` Symbolically: ```text EmptyBattery(R) → CannotMove(R) EmptyBattery(R) ∴ CannotMove(R) ``` Logic separates: ```text what we assume ``` from: ```text what necessarily follows ``` * * * # 16\. Propositional Logic The simplest major form is propositional logic. Statements are either: ```text TRUE FALSE ``` Example propositions: ```text R = It is raining W = The road is wet ``` You can write: ```text R → W ``` meaning: ```text IF raining THEN road wet ``` Common logical operators: ```text ¬P NOT P P ∧ Q P AND Q P ∨ Q P OR Q P → Q IF P THEN Q P ↔ Q P if and only if Q ``` * * * # 17\. First-Order Logic Propositional logic cannot naturally express: ```text Every human is mortal. ``` First-order logic introduces: * objects, * predicates, * variables, * quantifiers. Example: ```text Human(Socrates) ∀x Human(x) → Mortal(x) ``` Then: ```text Mortal(Socrates) ``` The symbol: ```text ∀x ``` means: ```text for every x ``` And: ```text ∃x ``` means: ```text there exists some x ``` First-order logic is dramatically more expressive than propositional logic. * * * # 18\. Inference Knowledge is what is stored. **Inference** is the process of deriving new knowledge from existing knowledge. Suppose the system knows: ```text A → B B → C A ``` It can infer: ```text B ``` then: ```text C ``` The database never explicitly contained: ```text C ``` But the system discovered it logically. That is inference. * * * # 19\. Forward Chaining Forward chaining starts with what you know and asks: > What else follows? Example: ```text BatteryEmpty(robot) BatteryEmpty(x) → CannotMove(x) CannotMove(x) → NeedsAssistance(x) ``` The system derives: ```text CannotMove(robot) NeedsAssistance(robot) ``` Think: ```text FACTS ↓ RULES ↓ MORE FACTS ``` * * * # 20\. Backward Chaining Backward chaining starts with a question. Suppose we want to prove: ```text NeedsAssistance(robot)? ``` The system asks: ```text What would make NeedsAssistance true? ``` Rule: ```text CannotMove(x) → NeedsAssistance(x) ``` So now it asks: ```text CannotMove(robot)? ``` That may require: ```text BatteryEmpty(robot)? ``` And that fact may already exist. Backward chaining works like investigating prerequisites. ```text GOAL ↑ what would prove it? ↑ what would prove that? ↑ known facts ``` Prolog famously uses this style of reasoning. * * * # 21\. The Problem With Pure Logic Logic is extremely powerful when the world is certain. But real intelligent systems rarely have perfect information. Imagine: ```text Camera detects something that looks 70% like a pedestrian. ``` Logic wants: ```text Pedestrian = TRUE or FALSE ``` Reality says: ```text Maybe. ``` This is where classical symbolic AI meets one of its biggest limitations. The real world contains: * noisy sensors, * incomplete information, * ambiguous observations, * random events, * unknown causes, * uncertain predictions. We need probability. * * * # 22\. Uncertainty Uncertainty is not merely ignorance. It is a fundamental engineering condition. An autonomous robot may be uncertain about: ```text Where am I? What object is that? Will that person cross? Is the floor slippery? Will this motor command succeed? ``` Intelligent systems must act **before uncertainty disappears**. That is important. AI rarely gets the luxury of saying: ```text I will make no decision until I know everything perfectly. ``` Often that would itself be a terrible decision. * * * # 23\. Probability as Belief Probability lets us represent degrees of belief. Instead of: ```text DoorBlocked = TRUE ``` we can represent: ```text P(DoorBlocked) = 0.7 ``` Meaning: > Given what I currently know, I assign a 70% probability to the door being blocked. If new information arrives, the probability can change. This ability to **update beliefs** is central to intelligent systems. * * * # 24\. Conditional Probability Suppose: ```text P(Rain) = 0.2 ``` But you see dark clouds. Now you want: ```text P(Rain | DarkClouds) ``` The vertical bar means: ```text given ``` So: ```text P(Rain | DarkClouds) ``` means: > Probability of rain given that dark clouds were observed. AI constantly reasons conditionally. ```text P(object is pedestrian | camera image) P(robot location | LiDAR measurements) P(disease | symptoms) P(user intent | conversation) ``` * * * # 25\. Bayes' Rule One equation deserves permanent residence in your engineering memory: ```text P(B | A) P(A) P(A | B) = -------------------------- P(B) ``` The conceptual form is more important: ```text Posterior ∝ Likelihood × Prior ``` Or: ```text NEW BELIEF = HOW WELL THE EVIDENCE FITS × WHAT YOU BELIEVED BEFORE ``` * * * ## Intuitive Bayesian example Suppose a robot thinks there is only a: ```text 1% chance ``` that a fire exists. Then its smoke sensor triggers. But smoke sensors occasionally produce false alarms. The robot should not automatically conclude: ```text FIRE! ``` It combines: ```text prior probability of fire ``` with: ```text probability that the sensor would trigger if there were a fire ``` and: ```text probability that it would trigger without a fire ``` to calculate a new belief. That updated belief is the **posterior**. Bayesian reasoning is fundamentally: > **belief revision after evidence arrives.** * * * # 26\. Bayesian Networks Now imagine many uncertain variables. Example: ```text Rain Sprinkler WetGrass SlipperyGround ``` They influence each other. A **Bayesian network** represents dependencies using a directed graph. ```text Rain / \ ▼ ▼ Sprinkler WetGrass \ / ▼ ▼ Slippery ``` More precisely, edges indicate probabilistic dependency. A classic example might be: ```text Rain ───────► WetGrass ▲ │ Sprinkler ─────┘ ``` Wet grass can be caused by either rain or the sprinkler. * * * # 27\. Why Bayesian Networks Matter Without structure, a joint probability distribution over many variables becomes gigantic. Suppose you have 100 binary variables. A naive table would require roughly: ```text 2^100 ``` possible combinations. That is astronomically large. Bayesian networks exploit conditional independence. For example: ```text Weather affects road slipperiness. Battery level probably does not. ``` So the AI does not need to model every variable as directly dependent on every other variable. Structure compresses probabilistic knowledge. This is the probabilistic version of a general engineering idea: > **Exploit structure instead of brute force.** * * * # 28\. Probabilistic Reasoning Probability representation is useful. But again we need **inference**. Suppose a Bayesian network contains: ```text Rain → WetRoad → AccidentRisk ``` We observe: ```text WetRoad = true ``` Now we can ask: ```text P(Rain | WetRoad) P(AccidentRisk | WetRoad) ``` This is probabilistic inference. Unlike logical inference: ```text A → B A therefore definitely B ``` probabilistic inference may say: ```text Given A, B is now 83% likely. ``` * * * # 29\. Logic vs Probability The difference is worth making crystal clear. Logic asks: > What must be true? Probability asks: > What is likely to be true? Logic: ```text All mammals breathe. Whale is a mammal. Therefore whale breathes. ``` Probability: ```text A blurry camera image resembles a bicycle. P(Bicycle | Image) = 0.82 ``` Modern intelligent systems often need both. * * * # 30\. From Beliefs to Decisions Knowing what might be true is not enough. Imagine: ```text 70% chance Path A is clear 100% chance Path B is clear ``` Which route should a robot choose? Probability alone cannot answer. We need information about: ```text cost reward risk preference value ``` That introduces **decision theory**. * * * # 31\. Decision Theory Decision theory combines: ```text uncertainty + preferences ``` to determine which action should be chosen. In simple form: ```text Expected Utility(action) = Σ P(outcome | action) × Utility(outcome) ``` Then choose: ```text action* = argmax ExpectedUtility(action) ``` This is one of the most important formulas in intelligent systems. In words: > Consider the possible outcomes of each action, weight each outcome by how likely it is, weight it again by how desirable it is, and choose the action with the best expected result. * * * # 32\. Expected Utility Example A robot can choose: ```text Shortcut SafeRoute ``` Shortcut: ```text 90% chance: arrive in 5 minutes 10% chance: become stuck ``` Safe route: ```text 100% chance: arrive in 12 minutes ``` Suppose utility is: ```text arrive quickly = +100 arrive slowly = +60 become stuck = -500 ``` Expected utility of shortcut: ```text 0.9 × 100 + 0.1 × (-500) = 90 - 50 = 40 ``` Safe route: ```text 1.0 × 60 = 60 ``` So despite being slower: ```text SafeRoute wins. ``` That is rational behavior under these preferences. * * * # 33\. Utility Theory Utility is a numerical representation of how desirable an outcome is to an agent. Example: ```text Reach destination +100 Use little energy +20 Collision -10000 Arrive 5 minutes late -10 Human injury -1000000 ``` Real systems often combine multiple objectives. For a delivery robot: ```text Utility = + delivery success - travel time - energy consumed - collision risk - discomfort to humans ``` This reveals something important: > **Intelligence cannot be separated entirely from objectives.** The same world model can produce completely different behavior depending on the utility function. * * * # 34\. Utility Is Not Simply Money Utility means: > preference expressed numerically. A safety-critical robot may value: ```text human safety ``` millions of times more strongly than: ```text saving 10 seconds. ``` A utility function encodes trade-offs. This is why objective design is such a difficult part of AI engineering. A badly specified objective may produce perfectly optimized but undesirable behavior. * * * # 35\. Planning Search asks: ```text What path reaches the goal? ``` Planning asks a richer question: > **What sequence of actions transforms the world from its current state into a desired state?** A planning system typically reasons about actions with: ```text preconditions effects ``` Example: ```text Action: PickUp(box) Precondition: RobotNear(box) GripperEmpty Effects: Holding(box) ¬GripperEmpty ``` Another action: ```text Place(box, shelf) Preconditions: Holding(box) RobotNear(shelf) Effects: BoxOnShelf GripperEmpty ``` The planner chains actions together. * * * # 36\. Planning Example Goal: ```text BoxOnShelf ``` Current state: ```text RobotNear(box) GripperEmpty BoxOnFloor ``` Possible plan: ```text PickUp(box) MoveTo(shelf) Place(box, shelf) ``` Notice the difference from simple pathfinding. Pathfinding mainly changes: ```text location ``` Planning may change many properties of the world: ```text location holding status doors open/closed objects moved machines activated resources consumed ``` * * * # 37\. Search vs Planning They are closely related. In fact, many planners internally use search. But conceptually: ```text SEARCH explores state space ``` while: ```text PLANNING reasons about action sequences and their effects ``` Planning gives meaning to the transitions. * * * # 38\. Deterministic Planning Has a Big Assumption Classical planning often assumes: ```text If I execute action A, effect B definitely occurs. ``` But robots live in a messier world. Suppose: ```text Action: MoveForward ``` Results: ```text 90% forward 7% slip 3% collision with obstacle ``` Now the future forms a branching probability tree. A fixed plan may no longer be sufficient. We need a policy. This leads to the **Markov Decision Process**. * * * # 39\. Markov Decision Process — MDP An MDP models sequential decision making under uncertainty. The key components are usually written: ```text (S, A, T, R, γ) ``` where: ```text S = states A = actions T = transition probabilities R = rewards γ = discount factor ``` Let's understand each. * * * # 40\. States A state represents the current situation. Example: ```text Robot at hallway Battery 40% Door closed ``` The important assumption in a standard MDP is the **Markov property**: > The current state contains everything relevant for predicting the next state. Meaning: ```text P(next state | entire history, current state, action) = P(next state | current state, action) ``` You do not need to remember the entire history if the present state is sufficiently informative. * * * # 41\. Actions Actions are choices available to the agent. Example: ```text move left move right charge wait open door ``` * * * # 42\. Transition Model The transition model describes how actions change the world. ```text T(s, a, s') ``` usually means: ```text P(next state = s' | current state = s, action = a) ``` Example: ```text MoveForward: 0.90 → next cell 0.05 → remain in place 0.05 → slip sideways ``` MDPs explicitly model the fact that actions may not produce deterministic results. * * * # 43\. Reward The reward function tells the agent what immediate outcomes are desirable. Example: ```text Reach goal +100 Collision -100 Every step -1 Recharge -5 ``` Why penalize each step? Because otherwise the robot may wander forever while still eventually reaching the goal. Reward shapes behavior. * * * # 44\. Discount Factor The discount factor: ```text γ ``` is usually between: ```text 0 and 1 ``` It determines how much future rewards matter. Total return may look like: ```text R₀ + γR₁ + γ²R₂ + γ³R₃ + ... ``` If: ```text γ ≈ 0 ``` the agent mostly cares about immediate rewards. If: ```text γ ≈ 1 ``` future consequences matter strongly. Think: ```text small gamma → impatient large gamma → farsighted ``` That intuition is enough. * * * # 45\. Policy This is one of the most important distinctions in AI. A **plan** might say: ```text Left Left Forward Right ``` A **policy** says: ```text IF state A → move left IF state B → move right IF battery low → charge IF obstacle appears → stop ``` Formally: ```text π(s) = action ``` or in stochastic policies: ```text π(a | s) ``` A policy is a strategy for choosing actions depending on what state actually occurs. This is ideal for uncertain environments because the agent adapts. * * * # 46\. Plan vs Policy Remember this permanently: ```text PLAN = "Do A, then B, then C." ``` ```text POLICY = "If this happens, do A. If that happens, do B." ``` A deterministic factory sequence may use a plan. An autonomous robot needs policies. * * * # 47\. Value Functions How good is a state? That is what a **value function** answers. ```text V(s) ``` means roughly: > expected future reward when starting from state `s` and behaving well. Similarly: ```text Q(s,a) ``` means: > expected future reward if I take action `a` in state `s`, then behave well afterward. This `Q` should sound familiar. It is the foundation of **Q-learning**. * * * # 48\. Bellman Thinking The deep idea behind value functions is recursive. The value of being somewhere is: ```text reward now + value of where you are likely to end up ``` Simplified: ```text V(s) = max_a [ reward + discounted expected future value ] ``` This is the essence of the **Bellman equation**. You do not need to memorize every variant. Remember the thought: > **A good decision considers both immediate reward and the quality of the future states it creates.** That principle appears everywhere in sequential decision making. * * * # 49\. Why MDPs Matter to Modern AI MDPs are not merely old textbook theory. They are the mathematical foundation of reinforcement learning. The relationship is roughly: ```text MDP = the problem Reinforcement Learning = methods for learning how to solve the problem ``` An MDP tells us: ```text states actions transitions rewards ``` RL asks: ```text How can an agent discover a good policy, perhaps without already knowing the transition dynamics? ``` * * * # 50\. The Hidden Assumption of an MDP MDPs assume the agent knows the current state. But consider a real robot. It receives: ```text camera images LiDAR IMU GPS microphone ``` It does not directly observe: ```text the complete true world state. ``` Instead, it gets incomplete and noisy measurements. This leads to the next model. * * * # 51\. POMDP — Partially Observable Markov Decision Process A POMDP is essentially: ```text MDP + hidden state ``` The real world has some state: ```text s ``` but the agent cannot directly see it. Instead it receives an observation: ```text o ``` Example: True world: ```text A person is behind a parked van. ``` Robot observation: ```text camera: van LiDAR: partial geometry ``` The robot cannot observe the hidden person directly. So rather than knowing the state, it maintains a **belief** over possible states. * * * # 52\. Belief State Suppose a robot is uncertain whether it is in hallway A or hallway B. It might maintain: ```text P(A) = 0.7 P(B) = 0.3 ``` This probability distribution is the robot's **belief state**. Then it receives a sensor measurement. After Bayesian updating: ```text P(A) = 0.2 P(B) = 0.8 ``` The belief changes. So a POMDP agent operates approximately like this: ```text Observation ↓ Update belief ↓ Choose action based on belief ↓ World changes ↓ New observation ``` That is extremely close to how real autonomous systems operate. * * * # 53\. POMDP Components A POMDP extends an MDP with observations. You can think of: ```text States Actions Transitions Rewards Observations Observation probabilities Beliefs ``` The observation model says: ```text P(observation | state) ``` For example: ```text If obstacle exists: LiDAR reports obstacle 95% of time. If no obstacle: LiDAR falsely reports obstacle 2% of time. ``` The system combines this with prior beliefs to estimate what is probably happening. * * * # 54\. MDP vs POMDP This distinction is worth burning into memory. ### MDP ```text I know exactly what state I am in. But actions may have uncertain results. ``` ### POMDP ```text I don't even know exactly what state I am in, and actions may also have uncertain results. ``` Examples: ```text MDP: video-game grid where complete state is available POMDP: physical robot operating through noisy sensors ``` The physical world is usually closer to a POMDP than a clean MDP. * * * # 55\. Why POMDPs Are Hard Suppose the physical world contains: ```text 1,000,000 possible states. ``` An MDP chooses actions over those states. But a POMDP maintains probabilities over all those states. So the effective state becomes something like: ```text [P(s₁), P(s₂), ..., P(s₁₀₀₀₀₀₀)] ``` This belief space can be enormous and continuous. Exact POMDP solutions quickly become computationally expensive. Real systems therefore use: * approximations, * particle filters, * learned policies, * state estimators, * receding-horizon methods, * hierarchical decision systems. This is a recurring engineering lesson: > The mathematically perfect solution is often computationally impossible, so intelligence becomes approximation under constraints. * * * # 56\. Decision Making Under Uncertainty Now many pieces can be assembled. Suppose an autonomous delivery robot sees something near the road. Its perception system says: ```text 70% pedestrian 20% sign 10% unknown ``` The robot can either: ```text continue slow stop ``` It must reason about consequences. Perhaps: ```text continue + pedestrian → catastrophic continue + sign → efficient stop + sign → minor delay stop + pedestrian → safe ``` Even if "pedestrian" is not the most certain interpretation, stopping may still have the greatest expected utility because the downside of being wrong is enormous. This explains something profound: > **The most probable world state does not automatically determine the best action.** Decision making requires both: ```text probability of outcome ``` and: ```text cost/value of outcome ``` * * * # 57\. Probability Is Not Utility Do not confuse: ```text What is likely? ``` with: ```text What is desirable? ``` Probability: ```text P(collision) = 0.01 ``` Utility: ```text Collision = -1,000,000 ``` A low-probability event can dominate a decision when its consequences are severe. That is why safety engineering cannot simply say: ```text "It's probably fine." ``` * * * # 58\. Expected Value Is Not Everything Either Basic decision theory often optimizes expected utility. But real engineering sometimes also considers: * worst-case risk, * variance, * safety constraints, * robustness, * uncertainty about the probability model itself, * human preferences, * irreversible outcomes. For example: ```text 99.9% chance of +$100 0.1% chance of killing someone ``` A naive reward function might behave terribly if the utilities are badly specified. Real autonomous systems therefore often combine: ```text optimization + hard constraints + safety rules + uncertainty handling ``` * * * # 59\. A Unified Robot Example Let's combine the entire chapter. Suppose we build: > **An autonomous hospital delivery robot.** It must deliver medicine. * * * ## Step 1 — Intelligent agent The robot is an agent. ```text Sensors → reasoning → actions ``` * * * ## Step 2 — Knowledge representation It represents: ```text rooms corridors doors patients staff charging stations objects relationships ``` Example: ```text Connected(RoomA, Corridor3) DoorBetween(RoomA, Corridor3) ``` * * * ## Step 3 — Logic Rules: ```text DoorLocked(x) → CannotTraverse(x) LowBattery(robot) → ShouldCharge(robot) ``` * * * ## Step 4 — Inference Given: ```text DoorLocked(D3) ``` infer: ```text CannotTraverse(D3) ``` * * * ## Step 5 — Search Find possible routes: ```text Pharmacy → corridor → elevator → Ward B ``` * * * ## Step 6 — Heuristic search A\* uses: ```text g(n) = travel cost so far h(n) = estimated distance remaining ``` to avoid exploring the entire hospital graph. * * * ## Step 7 — Constraint satisfaction Scheduling deliveries: ```text medicine A before 10:00 elevator unavailable 09:30–09:45 robot must charge before battery < 10% sterile delivery cannot pass through contaminated zone ``` This becomes a constraint problem. * * * ## Step 8 — Planning The robot constructs actions: ```text PickUpMedicine MoveToElevator CallElevator EnterElevator GoToFloor3 MoveToWard DeliverMedicine ``` * * * ## Step 9 — Uncertainty Camera sees a partially hidden object. ```text P(person) = 0.6 P(cart) = 0.3 P(other) = 0.1 ``` * * * ## Step 10 — Bayesian reasoning New LiDAR information arrives. Belief updates: ```text P(person) = 0.91 ``` * * * ## Step 11 — Bayesian network The system reasons about: ```text CrowdedHallway ↓ PersonDetected ↓ CollisionRisk ``` and other dependencies. * * * ## Step 12 — Decision theory Possible actions: ```text continue slow stop reroute ``` Expected consequences are compared. * * * ## Step 13 — Utility Preferences include: ```text + successful delivery + timeliness - energy consumption - patient disturbance - collision risk ``` Safety receives extremely large importance. * * * ## Step 14 — MDP Movement outcomes are uncertain. ```text Action: move forward 0.96 → success 0.03 → blocked 0.01 → localization problem ``` The robot uses a policy rather than one rigid plan. * * * ## Step 15 — POMDP The robot does not actually know the complete state. It maintains beliefs such as: ```text 70% corridor clear 25% hidden pedestrian 5% sensor malfunction ``` and continuously updates them. * * * That one robot contains almost the entire classical AI curriculum. * * * # 60\. The Deep Relationship Between All These Topics Here is the master map. ```text INTELLIGENT AGENT │ ▼ "What is happening?" │ ┌─────────────┴─────────────┐ │ │ CERTAIN WORLD UNCERTAIN WORLD │ │ LOGIC PROBABILITY │ │ INFERENCE BAYESIAN INFERENCE │ │ └─────────────┬─────────────┘ ▼ WORLD / BELIEF STATE │ ▼ "What can I do?" │ SEARCH / PLANNING │ ▼ POSSIBLE FUTURES │ ▼ "What do I want?" │ UTILITY │ ▼ DECISION THEORY │ ┌─────────┴─────────┐ │ │ fully observable partially observable │ │ MDP POMDP │ │ └─────────┬─────────┘ ▼ POLICY │ ▼ ACTION ``` If you understand this map, the individual terms stop feeling isolated. * * * # 61\. Another Way to Remember Everything Think of an intelligent agent as answering six questions. ## Question 1 ### Where am I? This involves: ```text perception state estimation knowledge representation probabilistic reasoning Bayesian inference ``` * * * ## Question 2 ### What is true? This involves: ```text logic knowledge representation inference ``` * * * ## Question 3 ### What could I do? This involves: ```text actions search planning constraint satisfaction ``` * * * ## Question 4 ### What could happen? This involves: ```text transition models probability uncertainty Bayesian reasoning MDPs POMDPs ``` * * * ## Question 5 ### What do I care about? This involves: ```text reward utility preferences objectives constraints ``` * * * ## Question 6 ### Therefore, what should I do? This involves: ```text decision theory planning policy optimization ``` That is classical AI compressed into six questions. * * * # 62\. Search, Planning, MDP and POMDP — The Progression These four concepts are often taught separately, which hides the beautiful progression. Start with: ## Search ```text I know where I am. I know the goal. Actions behave predictably. Find a path. ``` Then: ## Planning ```text I know where I am. Actions have preconditions and effects. Construct a useful action sequence. ``` Then: ## MDP ```text I know where I am. Actions may have uncertain results. Find a policy maximizing expected reward. ``` Then: ## POMDP ```text I don't know exactly where I am. My observations are uncertain. Actions may have uncertain results. Maintain beliefs and choose a policy. ``` In one line: ```text Search ↓ Planning ↓ Planning under stochastic outcomes ↓ MDP ↓ Decision making with hidden state ↓ POMDP ``` That progression is worth remembering. * * * # 63\. Logic → Probability → Decision Theory There is another beautiful progression. ## Logic ```text What follows from what I know? ``` Then reality introduces uncertainty. ## Probability ```text What is likely given what I know? ``` But probabilities alone cannot choose actions. So: ## Decision Theory ```text Given what is likely and what I value, what should I do? ``` Compressed: ```text LOGIC "What is true?" ↓ uncertainty PROBABILITY "What is likely?" ↓ preferences DECISION THEORY "What should I do?" ``` * * * # 64\. Deterministic AI vs Probabilistic AI Another useful mental division: ### Deterministic reasoning ```text If A, then B. ``` Examples: * logic, * classical planning, * deterministic search, * CSPs. ### Probabilistic reasoning ```text If A, B becomes more likely. ``` Examples: * Bayesian networks, * probabilistic inference, * MDPs, * POMDPs. Real autonomous systems usually contain both. Example: ```text Logic: If emergency_stop_pressed → motor_command = 0 Probability: P(pedestrian | camera) = 0.78 Decision: Given 78% pedestrian probability and enormous collision cost → stop. ``` That hybrid architecture is much closer to real engineering than imagining one single AI algorithm controls everything. * * * # 65\. What Modern Deep Learning Changed Modern machine learning did not make these ideas obsolete. Instead, it changed how some components are implemented. Older AI might explicitly build: ```text Dog(x) Animal(x) Inside(x, room) ``` Modern systems may learn internal representations from data. Older systems might manually construct heuristics. Modern systems may learn heuristics. Older systems might manually build transition models. Modern systems may learn them. But the underlying questions remain: ```text What state am I in? What might happen? What action should I choose? What outcome do I value? ``` Deep neural networks did not remove the problem of intelligent decision making. They gave us dramatically better tools for: ```text perception representation prediction generation approximation ``` * * * # 66\. LLM Agents Through Classical AI Eyes Modern LLM agents become much easier to understand through these foundations. Suppose an AI coding agent receives: ```text "Fix the failing authentication test." ``` It may maintain: ### State ```text repository contents test failures conversation tool outputs ``` ### Actions ```text read file search code edit code run test inspect logs ``` ### Search It explores possible explanations. ```text Maybe token validation is wrong. Maybe middleware order is wrong. Maybe the test fixture is wrong. ``` ### Heuristic It prioritizes hypotheses that seem more likely. ### Knowledge representation Its context contains code, requirements, and inferred relationships. ### Inference It concludes: ```text The request reaches middleware before the auth token is injected. ``` ### Planning ```text Inspect middleware → patch function → run focused test → run wider suite ``` ### Uncertainty It is not certain the first hypothesis is correct. ### Utility/objective ```text fix bug avoid regressions minimize unnecessary edits ``` ### Policy After every tool result, it decides what to do next. Modern "agentic AI" is new technology built on very old questions. * * * # 67\. Autonomous Robots Through Classical AI Eyes A sophisticated robot may contain: ```text Neural perception ↓ State estimation ↓ Probabilistic world model ↓ Planning ↓ Decision making ↓ Control ``` For example: ```text Camera + LiDAR ↓ Detect pedestrian ↓ Estimate position + uncertainty ↓ Predict possible pedestrian motion ↓ Evaluate candidate trajectories ↓ Choose safe trajectory ↓ Controller executes it ``` Notice that the neural network is only one part. The robot still needs: * state, * uncertainty, * prediction, * objectives, * planning, * action selection, * feedback. That is why classical AI foundations remain valuable to a robotics/AI engineer. * * * # 68\. A Critical Engineering Distinction: Model vs Agent This distinction is increasingly important. A **model** computes something. ```text input → output ``` Example: ```text image → pedestrian probability ``` An **agent** participates in a loop. ```text observe ↓ reason ↓ act ↓ observe consequences ↓ reason again ``` A model can be part of an agent. For example: ```text YOLO ``` may detect objects. But YOLO itself does not decide: ```text Should the robot brake? ``` That decision belongs to a larger agent architecture. * * * # 69\. Another Critical Distinction: Prediction vs Decision Suppose an AI predicts: ```text P(stock rises tomorrow) = 55% ``` That does NOT automatically mean: ```text BUY. ``` The decision depends on: ```text potential upside potential downside transaction cost risk tolerance alternative investments uncertainty ``` Similarly: ```text P(pedestrian) = 40% ``` might still justify braking. Prediction asks: ```text What will happen? ``` Decision asks: ```text What should I do about it? ``` Never confuse them. * * * # 70\. Another Critical Distinction: Reward vs Goal A goal might be: ```text reach destination ``` But a reward function must often capture much more: ```text +100 destination reached -1 each second -20 excessive energy -100 collision -100000 human injury ``` If you simply reward: ```text reach destination ``` the AI may discover absurd strategies. This is related to: * reward hacking, * specification gaming, * alignment problems. The optimization algorithm does not automatically understand your intentions. It understands the objective you actually encoded. * * * # 71\. The Engineering Principle Behind Heuristics Why are heuristics so important? Because intelligence operates under finite compute. Suppose a problem has: ```text 10^50 ``` possible solutions. Brute force says: ```text Try all of them. ``` Impossible. A heuristic says: ```text These 1000 possibilities look much more promising. ``` This pattern appears everywhere: ```text Search heuristics Attention Pruning Beam search Candidate generation Retrieval Planning heuristics Approximate inference Sampling ``` Many AI breakthroughs can be viewed partly as: > **Find a better way to allocate limited computation toward promising possibilities.** * * * # 72\. The Engineering Principle Behind Probability Probability solves another fundamental limitation: ```text We never know everything. ``` Instead of forcing the world into: ```text TRUE FALSE ``` probabilistic systems can maintain: ```text unlikely possible likely almost certain ``` More importantly, they can revise beliefs when evidence arrives. That makes probability one of the natural mathematical languages of autonomous intelligence. * * * # 73\. The Engineering Principle Behind Utility Suppose two engineers build agents with identical world models. Agent A optimizes: ```text speed ``` Agent B optimizes: ```text safety ``` They may behave completely differently. Therefore: > A world model tells an agent what the world is like. A utility function tells the agent what kind of world it should try to create. This distinction becomes extremely important in AI safety and alignment. * * * # 74\. The Engineering Principle Behind Planning Reactive behavior says: ```text Obstacle → turn. ``` Planning says: ```text If I turn here, then I enter corridor B, which eventually lets me reach the destination. ``` Planning introduces **foresight**. An intelligent system becomes more powerful when it can reason not merely: ```text What action looks good now? ``` but: ```text What sequence of consequences will this action create? ``` * * * # 75\. The Engineering Principle Behind MDPs MDPs add an even deeper idea: > An action should be judged partly by the future decisions it enables. Imagine: ```text Action A gives +10 immediately but traps you. Action B gives +1 immediately but enters a state where +100 becomes possible. ``` A purely greedy agent chooses A. A farsighted agent chooses B. This is why: ```text immediate reward ``` is not the same as: ```text long-term value. ``` * * * # 76\. The Engineering Principle Behind POMDPs POMDPs introduce one more profound idea: > Sometimes the correct action is valuable because it gives you information. Imagine a robot unsure whether a room contains a person. It could: ```text enter immediately ``` or: ```text move slightly left to get a better camera angle. ``` The second action may not move toward the physical goal. But it reduces uncertainty. This is called **information gathering**. An intelligent agent sometimes acts not to change the world directly, but to **learn more about the world**. That is a very important property of advanced autonomy. * * * # 77\. Exploration vs Exploitation This naturally leads to another major AI concept. Suppose a robot knows: ```text Route A usually works. ``` There is also: ```text Route B ``` which it has never tried. Should it: ```text exploit ``` the known good route? Or: ```text explore ``` the unknown route because it might be better? This is the **exploration–exploitation trade-off**. It appears in: * reinforcement learning, * recommendation systems, * robotics, * clinical trials, * online advertising, * scientific discovery. Intelligence must sometimes sacrifice immediate certainty to acquire information that improves future decisions. * * * # 78\. Classical AI in One Mathematical Story We can now express the entire field surprisingly compactly. The agent has some information: ```text I ``` It uses that information to maintain beliefs: ```text P(state | I) ``` For each action: ```text a ``` it predicts possible outcomes: ```text P(outcome | state, action) ``` Each outcome has some value: ```text U(outcome) ``` The agent seeks an action maximizing expected utility: ```text a* = argmax_a E[U | a, I] ``` Sequential environments extend this over future states and actions. That basic structure contains much of: * Bayesian decision theory, * MDPs, * POMDPs, * reinforcement learning, * autonomous decision making. * * * # 79\. The Most Important Conceptual Ladder If you ever forget the details, reconstruct the field using this ladder: ```text 1. STATE What situation am I in? 2. KNOWLEDGE What do I know about it? 3. INFERENCE What else follows from what I know? 4. UNCERTAINTY What am I unsure about? 5. BELIEF How likely are the possibilities? 6. ACTIONS What can I do? 7. TRANSITIONS What might each action cause? 8. UTILITY Which outcomes do I prefer? 9. SEARCH / PLANNING Which future possibilities should I consider? 10. DECISION Which action is best? 11. POLICY What should I do as situations change? 12. FEEDBACK What did the world actually do? 13. UPDATE What should I now believe? 14. REPEAT ``` That loop is autonomous intelligence. * * * # 80\. Your Permanent Cheat Sheet ## Intelligent Agent ```text Observe → Reason → Act → Repeat ``` * * * ## Search ```text Explore possible states to reach a goal. ``` * * * ## Heuristic Search ```text Use an estimate to explore promising states first. ``` * * * ## A\* ```text f(n) = g(n) + h(n) actual cost so far + estimated remaining cost ``` * * * ## Constraint Satisfaction ```text Variables + Domains + Constraints → valid assignment ``` * * * ## Knowledge Representation ```text Encode facts, objects, relationships, rules and structure so machines can reason about them. ``` * * * ## Logic ```text What MUST follow from what I know? ``` * * * ## Inference ```text Derive new conclusions from existing knowledge. ``` * * * ## Probability ```text Represent uncertainty numerically. ``` * * * ## Bayesian Reasoning ```text Posterior ∝ Likelihood × Prior new belief = evidence × old belief ``` * * * ## Bayesian Network ```text Graph representing probabilistic dependencies between variables. ``` * * * ## Decision Theory ```text Probability + Utility → Rational Action ``` * * * ## Utility ```text How desirable is an outcome? ``` * * * ## Expected Utility ```text EU(action) = Σ probability(outcome) × utility(outcome) ``` * * * ## Planning ```text Find an action sequence that transforms the current world into a desired world. ``` * * * ## MDP ```text Known state + uncertain action outcomes + rewards → optimal policy ``` Remember: ```text S A T R γ ``` ```text State Action Transition Reward Discount ``` * * * ## Policy ```text State → Action ``` Not: ```text one fixed sequence ``` but: ```text what to do depending on what happens. ``` * * * ## Value ```text V(s) = how good it is to be in state s, considering the future. ``` * * * ## Q-value ```text Q(s,a) = how good action a is when taken from state s, considering future rewards. ``` * * * ## POMDP ```text MDP + you cannot directly observe the true state. ``` Therefore maintain: ```text belief state = probability distribution over possible states. ``` * * * ## Uncertainty ```text The agent does not know the world perfectly. ``` * * * ## The complete formula in English ```text Observe the world. Represent what you know. Infer what may be true. Represent uncertainty. Predict possible futures. Search through useful possibilities. Understand what outcomes you value. Choose the action with the best expected long-term outcome. Observe what happened. Update your beliefs. Repeat. ``` * * * # Final Mental Picture When people hear **Artificial Intelligence**, they often imagine: ```text a neural network ``` or: ```text an LLM ``` But the deeper engineering picture is much broader. An intelligent autonomous system must continually solve: ```text PERCEPTION "What did I observe?" ↓ REPRESENTATION "What does the world currently look like?" ↓ INFERENCE "What can I conclude?" ↓ UNCERTAINTY "What am I not sure about?" ↓ PREDICTION "What might happen next?" ↓ SEARCH / PLANNING "What possible actions and futures exist?" ↓ UTILITY "Which outcomes matter?" ↓ DECISION "What should I do?" ↓ ACTION "Execute it." ↓ FEEDBACK "What actually happened?" ↓ BELIEF UPDATE "What should I now believe?" ↓ REPEAT ``` That loop is the heart of autonomous intelligence. And almost every advanced system you encounter—from a warehouse robot, to an autonomous vehicle, to a game-playing agent, to an AI coding agent—can be understood by asking where each of these responsibilities exists inside the architecture. If you forget individual equations later, remember this: > **AI is not merely prediction. AI is the engineering of good decisions from limited information, limited computation, uncertain worlds, and explicit objectives.** Once that sentence feels obvious, the rest of classical AI has somewhere to live in your head.