Intelligent Agents

• Intelligent agents perceive their environment through sensors and act upon it using actuators.
• An agent's structure consists of its architecture and its agent program.
• Architecture is the hardware or computational framework.
• Agent program is the software that controls decision-making.
• Together, these components map percepts (sensory inputs) to actions rationally. Agent programs dictate how percepts are processed and actions are selected.
• There are five primary agent types.

Simple Reflex Agents

• Actions are selected based solely on the current percept, disregarding past history.
• Condition-action rules, or if-then rules, are utilized.
• It is efficient in fully observable environments but ineffective in partially observable ones.

Model-Based Agents

• Maintains an internal state that relies on percept history, reflecting unobserved aspects of the current state, to handle partial observability.
• Needs knowledge about how the world evolves independently and how the agent's actions affect the world.
• Knowledge about how the world works is known as a model of the world.
• Agents using such models are called model-based agents.

Goal-Based Agents

• Requires goal information describing desirable situations in addition to a current state description to make decisions.
• Goal-based action selection is straightforward when a single action leads to immediate goal satisfaction.
• AI subfields like search and planning help find action sequences that achieve the agent's goals.
• While seeming less efficient, it offers more flexibility since decisions are explicitly represented and modifiable.

Utility-Based Agents

• A utility function internalizes the performance measure.
• Actions are chosen to maximize this metric.
• Provide high-quality behavior in most environments as goals alone are inadequate

Learning Agents

• Learning agents improve their competence over time, even in initially unknown environments.
• A learning agent consists of four conceptual components:
• Performance element executes decisions.
• Learning element updates behavior using feedback.
• Critic evaluates performance.
• Problem generator suggests exploration.
• Learning is a process of modifying agent components to align with available feedback information, thus improving overall performance

Well-Defined Problems and Solutions

• Five components define a problem formally:
• Initial state: where the agent begins, e.g., In(Arad).
• Actions: possible actions available to the agent in a state s, with ACTIONS(s) returning the applicable actions, e.g., {Go(Sibiu), Go(Timisoara), Go(Zerind)} from In(Arad).
• Transition model: describes what each action does, using RESULT(s, a) to return the state resulting from action a in state s, with the term successor referring to states reachable by a single action.
• Goal test: determines if a given state is a goal state, e.g., {In(Bucharest)}.
• Path cost function: assigns a numeric cost to each path, reflecting the agent's performance measure, with the step cost from state s to s' via action a denoted as c(s, a, s').

Example Problems

Vacuum World:

• States: Agent location and dirt presence, totaling 8 states for two locations.
• Initial state: Any state can be initial.
• Actions: Left, Right, Suck.
• Transition model: Actions have expected effects, with exceptions for boundary and clean squares.
• Goal test: All squares are clean.
• Path cost: Each step costs 1.

8-Puzzle

• States: Tile locations, with nine squares in total
• Initial state: Any state possible, although only half can reach a given goal.
• Actions: Movements of the blank space: Left, Right, Up, Down.
• Transition model: Returns the state resulting from the action.
• Goal test: Matches the goal configuration.
• Path cost: Each step costs 1.

Solving Problems by Searching

• Search algorithms find solutions by considering action sequences, forming a search tree rooted at the initial state.
• Branches are actions, and nodes are states.
• The frontier is the set of leaf nodes available for expansion.
• Search algorithms expand nodes on the frontier until a solution is found, or there are no more states to expand.
• Search strategies vary on how they choose the next state to expand.
• Repeated states: Paths can loop (e.g., Arad to Sibiu back to Arad).
• Redundant paths: Multiple ways to get from one state to another.
• Explored set: Augments with the TREE-SEARCH algorithm via data structure to remember every expanded node.
• Newly generated nodes matching previous ones are discarded from the frontier.
• GRAPH-SEARCH: is the new algorithm.

Infrastructure for Search Algorithms

• Data structure is required to track the search tree being constructed. For each node n, it consists of:
• STATE: the state in the state space.
• PARENT: the generating node.
• ACTION: Action applied from parent.
• PATH-COST: Cost from initial state to node, denoted by g(n).

Uninformed Search Strategies

• Uninformed search (blind or brute-force) uses no additional information beyond the problem definition, and the strategies are distinguished by node expansion order.

Breadth-First Search (BFS)

• Expands the root node first, then all successors, and so on, expanding all nodes at a given depth before the next level.
• Achieved using a FIFO queue for the frontier.
• The goal test is applied when a node is generated.
• Discards new paths to states already in the frontier or explored set, as they are at least as deep as existing paths.

Depth-First Search (DFS)

• Always expands the deepest node in the current frontier.
• Uses a LIFO queue (stack), choosing the most recently generated (deepest) node.
• The properties depend on graph-search or tree-search version used.
• The graph-search version is complete in finite state spaces.
• Tree-search version can loop infinitely.
• DFS can check against states on the root path to prevent loops but not redundant paths.
• Returns all paths and determines path existence between nodes, and if the output is null, then there are no paths available

Iterative Deepening Search (IDS)

• It combines the benefits of depth-first and breadth-first search
• Limited search depth is gradually increased (0, 1, 2, etc.) until a goal is found.
• Memory efficient, as is the depth-first search.
• Complete when the branching factor is finite and optimal when the path cost is a nondecreasing function of the depth of the node (like breadth-first search).
• It is preferred for large search spaces when the solution depth is unknown.