| Concept | Note |
| --------------------- | :------------------------------------------------------------------------------------------------------------------- |
| Agent | an entity that perceives and acts |
| Rational | Doing the right thing |
| Actuator | A means of acting upon the environment |
| Sensor | A means of capturing percepts |
| Agent function | Maps percept sequence to action |
| Agent program | Implements agent function |
| Consequentialism | Evaluating behavior by its consequences |
| Rational agent | For each possible percept sequence, it selects the action that maximizes expected performance |
| Omniscience | Knowing the actual outcome of actions |
| Information gathering | Doing actions to modify future percepts |
| Environment types | |
| Fully observable | Environment where state is visible |
| Partially observable | Environment where parts of a state are visible |
| Unobservable | No sensors |
| Single-agent | Contains only one agent |
| Multi-agent | 2+ agents, competitive, cooperative |
| Deterministic | Next state is completely determined by the current state and action |
| Stochastic | Explicit probabilities |
| Nondeterministic | Not deterministic |
| Episodic | Current action doesn’t affect future decisions |
| Sequential | Current decision may affect future decisions |
| Dynamic | Env changes while agent thinks |
| Static | Not dynamic |
| Semi-dynamic | Env doesn't change but performance changes |
| Discrete | Countable states, percepts, actions |
| Continuous | Not discrete |
| Known | Actions and outcomes are known |
| Unknown | Not known/partially known |
| Agent types | |
| Simple reflex agent | Condition-action rules map percepts to actions |
| Model-based agent | Keeps state and/or change of state info, how actions change the state + reflex |
| Goal-based agent | Model based + what the world is like now, what it will be like if it acts. Replace condition-action rules with goals |
| Utility-based agent | Goal based - goal + utility (how happy itll be in a future state) |
| Learning agent | Critic, learning element, performance element, problem generator, performance standard outside of agent |
**Env-action representation**
Atomic representation:
```mermaid
graph LR
B[B] -- action --> C[C]
style B fill:#e1d5e7,stroke:#333,stroke-width:2px
style C fill:#e1d5e7,stroke:#333,stroke-width:2px
```
Factored representation:
```mermaid
graph TD
subgraph B [State B]
direction TB
v1((●))
v2((○))
v3((●))
v4((○))
bar1[████░░]
bar2[██████]
end
B --> C
subgraph C [State C]
direction TB
u1((○))
u2((○))
u3((●))
u4((●))
c_bar1[████░░]
c_bar2[█░░░░░]
end
style B fill:#e1d5e7,stroke:#333,stroke-width:2px
style C fill:#e1d5e7,stroke:#333,stroke-width:2px
```
Structured representation:
```mermaid
graph LR
subgraph B [State B]
direction TB
o1[■] --> o2[■]
o1 --> o3[■]
o3 --> o4[□]
o2 --> o4
end
B --> C
subgraph C [State C]
direction TB
r1[□] --> r2[■]
r1 --> r3[■]
r2 --> r4[□]
r3 --> r4
end
style B fill:#e1d5e7,stroke:#333,stroke-width:2px
style C fill:#e1d5e7,stroke:#333,stroke-width:2px
style o1 fill:#b85450,color:white
style o2 fill:#008080,color:white
style o3 fill:#b85450,color:white
style o4 fill:#fff
style r2 fill:#008080,color:white
style r3 fill:#b85450,color:white
```
![[Goal-based agents representation]]
| | |
| ------------------------------------ | ------------------------------------------------------------------------------------------------------------------------------------------ |
| Tree search | Init, serve, taste, goal test, serve |
| Graph search | Init, serve, taste, goal test, explored, serve if not explored or served |
| Repeated state | Same state different node |
| Loopy path | Path from state to itself |
| Redundant path | More than one way to get from a to b |
| BFS | Complete, optimal for unicost, O(b^d), O(b^d) |
| DFS | Not complete, not optimal, O(b^m), O(bm) |
| DLS | DFS till depth limit |
| IDS | Complete, Optimal for unicost, -> O(b^d), O(bd) |
| UCS | f(n) = g(n) |
| Greedy best-first | f(n) = h(n)<br><br>Not complete, not optimal, O(b^m), O(b^m) |
| Admissible heuristic | Never overestimates cost to goal |
| Consistent heuristic | h ≤ action + new state h |
| A* | Complete, Optimal, O(b^(ed)) O(# of nodes)<br><br>a*(n) = path(n) + h(n) |
| Hill climb | Gradient ascent generalized to discrete env |
| Minimax | O(bm) |
| A-b pruning<br><br>O(bm/2), O(b3m/4) | Alpha = best for max<br><br>Beta = best for min |
| CSP | Vards, domains, constraints |
| Node-consistent | Domain satisfies unary constraints |
| Arc-consistent | Domain satisfies binary constraints |
| AC3 | O(cd^3) d = domain size, c = constraints |
| Min remaining vals heur | Var with fewest legal vals |
| Degree heur | Var with largest number of constraints |
| Least-constraining val heur | Val with least ruled out choices |
| Forward checking | Assign a value to a var and update domains, repeat |
| Local Search | complete-state formulation: the initial state assigns a value to each variable, and the search changes the value of one variable at a time |
| Min-conflicts heur | Val with min conflicts with other vars |
| Subproblem solving csp | O(dc * n/c), n/c subproblems |
| Constraint graph = tree | O(nd2) |
| Cycle cutset | Removing it leaves us with a tree O(dc(n-c)d2) |
| Tree width | Size of largest node - 1 |
| Soundness | If derived then entailed |
| Completeness | If entailed then derived |
| Operator precedence | $\neg, \land, \lor, \implies, \iff$ |
|Valid|True for all models|
|satisfiable|True for some model|
|Reductio ad absurdum|KB and not a is invalid|
|Modus Ponens|Method of affirming|
Types of clauses:
- **Definite clause:** a disjunction of literals of which exactly one is positive, e.g. (¬L1,1∨¬Breeze∨B1,1)(¬L1,1∨¬Breeze∨B1,1)
- **Horn clause:** a disjunction of literals of which at most one is positive
- **Goal clause:** a disjunction with no positive literals
- **k-CNF:** a CNF sentence where each clause has at most k literals
Propositional logic: declarative, allows partial/disjunctive/negated, compositional, context-independent, limited expressive power
- **atomic sentences:** a single propositional symbol that can be either True or False, e.g.
True,False,P,Q,R,W1,3,FacingEast
- **complex sentences:** constructed from simpler sentences, using parentheses and logical connectives
- **connectives:** negation ¬, conjunction ∧, disjunction ∨, implication ⟹, biconditional ⟺
- **literals:** an atomic sentence (positive literal) or a negated atomic sentence (negative literal), e.g.
P,¬PP,¬P
| Concept | Note |
| --------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| PL-resolution | Prove (KB and not a) is unsat by looping thru each pair of clauses |
| Pure symbol | Always with same sign |
| DPLL | Depth first recursive, takes cnf, determines SAT |
| Unit clause heuristic | Assign all unit clauses first |
| Component analysis | Splitting a problem into independent subproblems through assignment of some variables, and solving the subproblems efficiently |
| Variable and value ordering | Non-arbitrary way of choosing variables and values to be assigned next. The degree heuristic chooses the variable that appears most frequently over all remaining clauses |
| Intelligent backtracking | Backing up all the way to the relevant point of conflict instead of chronological backtracking |
| Random restarts | If no visible progress is observed, start over from the top of the search tree, with different random choices made after that |
| Clever indexing | The indexing structures must be updated dynamically as the computation proceeds |
| SAT problems | Can get solved by hill-climbing, sim-annealing or other local search strats |
| Fluent | State variable |
| Atemporal variable | Not fluent |
| Effect axiom | States preconds and changes |
| Frame axiom | States what doesn’t change |
| Successor-state axiom | Had arrow and not shot at t - 1 -> have arrow |
| Precondition axiom | Shoot at t implies have arrow at t |
| **Objects** | people, houses, numbers, theories, Ronald McDonald, <br>colors, baseball games, wars, centuries, ... |
| **Relations** **unary** | relations or properties such as red, round, <br>prime, ..., or more general **n-ary** relations such as: brother of, bigger than, inside, part of, has color, occurred after, owns, comes between, ... |
| **Functions** | father of, one more than, beginning of ... |
|DB Semantics|Unique names, not known assumed false, no more domain elements|
|Diagnostic rule|infer cause from effect|
|Causal rule|Infer effect from cause|
|Skolem constant|In prop logic, some constant that exists out there|
|Semidecidable|Algos can infer if yes but cant if no|
|FO definite clause|Disjunctions of literals where only 1 is positive<br><br>Existential not allowed, Universal is implied|
|Fixed point|No more inferences to do|
|PDDL for planning|No negations, fluents, functions|
|State abstraction|Limit cargo to only 5 airports|
|Total-order planner|Maintains ordering of plan steps|
|Slack|LS - ES|
|Downward refinement property|At least one implementation achieves goal|