Grundlagen der KI an der TU München

Rationality

A system is rational if it does the “right thing”, i.e., has an ideal performance (performance measures are not always available).

Rational Agent

For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the prior percept sequence and its built-in knowledge.

Omniscient agent

An omniscient agent knows the actual outcome of its actions, which is impossible in reality.

Example: Just imagine you know the outcome of betting money on something.

A rational agent (!= omniscient agent) maximizes expected performance.

Learning

Rational agents are able to learn from perception, i.e., they improve their knowledge of the environment over time.

Autonomy

In AI, a rational agent is considered more autonomous if it is less dependent on prior knowledge and uses newly learned abilities instead.

An environment is fully observable if the agent can detect the complete state of the environment, and partially observable otherwise.

Example: The vacuum-cleaner world is partially observable since the robot only knows whether the current square is dirty.

Fully observable often in games

An environment is a multi agent environment if it contains several agents, and a single agent environment otherwise.

Example: The vacuum-cleaner world is a single agent environment. A chess game is a two-agent environment.

An environment is deterministic if its next state is fully determined by its current state and the action of the agent (outcome of an action is known), and stochastic otherwise.

Example: The automated taxi driver environment is stochastic since the behavior of other traffic participants is unpredictable. The outcome of a calculator is deterministic.

An environment is episodic if the actions taken in one episode (in which the robot senses and acts) does not affect later episodes, and sequential otherwise.

Example: Detecting defective parts on a conveyor belt is episodic. Chess and automated taxi driving are sequential.

If an environment only changes based on actions of the agent, it is static, and dynamic otherwise.

Example: The automated taxi driver environment is dynamic. A crossword puzzle / chess is static.

An environment is known if the agent knows the outcomes (or outcome probabilities) of its actions, and unknown otherwise. In the latter case, the agent has to learn the environment first.

Example: The agent knows all the rules of a card game it should play, thus it is in a known environment. Also autonomous driving is known (proabilities)

Four categores with increasing generalitiy:

• simple reflex agents,
• reflex agents with state,
• goal-based agents,
• utility-based agents.

All these can be turned into learning agents.

Examples of Real-World Problems

• Route-Finding problem: Airline travel planning, video streams in computer networks, etc.
• Touring problem: How to best visit a number of places, e.g., in the map of Romania?
• Layout of digital circuits: How to best place components and their connections on a circuit board?
• Robot navigation: Similar to the route-finding problem, but in a continuous space.
• Automatic assembly sequencing: In which order should a product be assembled?
• Protein design: What sequence of amino acids will fold into a three-dimensional protein?

Depth-Limited Search: Idea

• Shortcoming in depth-first search: Depth-first search does not terminate in infinite state spaces. Why?
• Solution: Introduce depth limit l. (could be too low)
• New issue: How to choose the depth-limit?

Uninformed search

• No additional information besides the problem statement (states, initial state, actions, transition model, goal test) is provided.
• Uninformed search can only produce next states and check whether it is a goal state.

Informed search

• Strategies know whether a state is more promising than another to reach a goal.
• Informed search uses measures to indicate the distance to a goal.