Agent Internals
Roope Raisamo (rr@cs.uta.fi) Dept. of Computer and Information Sciences University of Tampere
http://www.cs.uta.fi/~rr/
Agent Internals
Roope Raisamo (rr@cs.uta.fi) Dept. of Computer and Information Sciences University of Tampere
http://www.cs.uta.fi/~rr/
Introduction
This lecture is a brief survey on some artificial intelligence techniques that can be applied in software agents. The main references are the following books:
Bigus & Bigus, Constructing Intelligent Agents with Java. John Wiley & Sons, 1998.
Watson, Intelligent Java Applications. Morgan-Kaufmann, 1997.
Problem solving using search strategies
How to present a problem so that the computer can solve it?
A solution: to present the problem as states and to solve the problem using search techniques.
State space
the initial state and the set of possible operators
the allowed operators are applied to the initial state which results in a certain path in state space
the problem: how to identify the goal state?
Search strategies
If problem-specific information is not used the search is usually inefficient
so called brute-force, uninformed, or blind search
Problem-specific information makes the search more efficient
heuristic, informed, or directed search
course Algoritmien suunnittelu ja analyysi
Heuristic search techniques
NP complete problems do not make it possible to find the best solution in reasonable time, so we need to be content in a good solution
Heuristic solutions
Generating and testing solutions: choose the first solution that solves the problem
”Mountain hiking”: compare the generated solution to the goal by measuring the estimated distance from the goal (can be a local minimum or a local maximum)
Randomization, introducing disturbance
Heuristic search techniques
Greedy search: go always to the direction that looks best
A* Search takes into account the following:
an estimate of costs that are needed to move from the current state to the goal state
an estimate of costs that are needed to move from the initial state to the state n
Constraint solving -- fulfulling the constraints
The selected set of constraints determines acceptable solutions
Means-ends analysis (Newell and Simon, 1963)
A simple solution (Rick and Knight, 1991):
1. Compare the current state C to the result state G. If they are equal, the search is complete.
2. Choose the most important difference compared to the result state and make it smaller with the following steps:
(on the next slide)
Means-ends analysis (Newell and Simon, 1963)
a) Choose an operator that refers to the difference. In case no suitable operator exists, the search is ended as a failure.
b) Try to apply the chosen operator to state C by generating two temporary states: one in which the preconditions of the operators are true (prestate, P1) and another that is the state after the chosen operator is applied to state C (poststate, P2)
c) Divide the problem in two parts: C --> P1 ja P2 --> G. Call this algorithm recursively to both parts. If both are solvable, the solution is C-->P1 op P2-->G
Presenting the knowledge
How to present information on the problem domain in the application?
a solution: use symbols (e.g., representing objects or ideas with strings or numbers)
natural language would be the best way for humans to present this information by it is not that in computer programs
Procedural representation
Information and related operations
Easy to program
Hard-coded knowledge, usually not adaptable without program code changes
Attaches the information and its operations strictly together
An option is declarative representation: we list facts, rules, and the relationships between them.
Relational representation
As in relational databases
The information is stored in tables in which required searches are conducted using a database system and SQL language, for example.
Are not suitable to represent complex relationships and can be inefficient
Hierarchical representation
Inheritance of knowledge ”football is-a ball”
Makes it possible to apply algorithms in several levels of abstraction (and detail)
Is especially suitable to be used with object-oriented software techniques and object-oriented databases
Predicate logic
course Logiikkaohjelmointi, spring 2002
Clauses describe the state of the world
Minnesota is cold in the winter: place(Minnesota) and temperature(cold) and season(winter) cold(Minnesota, winter) winter(Minnesota,cold)
Predicate logic
The manipulation of information and the generation of new facts:
proving things right or wrong (resolution) using the method of proving the negation false
combining several clauses (unification)
replacing a variable with a constant, replacing a variable with another variable, and replacing a variable with a predicate
The base for the Prolog language that is based on logic programming paradigm
Deduction systems
Rule-based deduction (if-then)
Forward Chaining (inferencing)
Backward Chaining (goal-directed inferencing)
Fuzzy Logic
the truth value may be anything that [0.0, 1.0]
Planning
course Tekoälyn ohjelmointimenetelmät
Learning systems
Learning paradigms
guided learning, learning based on examples
undirected learning, detecting the similarities in the input or detecting features in the input
re-enforced learning when the result is not clear
Neural networks
===> course Neuroverkot
Decision trees
based on the information theory
Learning systems
Classifiers
learning for rule-based systems
genetic algorithms
===> course Algoritmien suunnittelu ja analyysi
This is only a brief introduction to the techniques; those who are interested may want to take part in the course Tekoälyn ohjelmointimenetelmät
Comments