Knowledge-Based Agents?
Knowledge base = set of sentences in a formal language.
Agents can be viewed at the knowledge level or at the implementation level.
knowledge level: what they know and implementation level: algorithms that manipulate them.
The agent must be able to:
- represent states, actions, etc
- incorporate new percepts
- update internal representations of the world
- deduce hidden properties of the world
- deduce appropriate actions
A simple Knowledge-Based Agent?
function KB-Agent(percept) returns an action
static: KB, a knowledge base
t, a counter, initially 0, indication time
TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))
action
how logical agents derive new information and make decisions?
logical agents apply inference to a knowledge base
basic concepts of logic:
- syntax: formal structure of sentences
- semantics: truth of sentences in the models
- entailment: necessary truth of one sentence given another
- inference: deriving sentences from other sentences
- soundness: derivations produce only entailed sentences
- completeness: derivations can produce all entailed sentences
British Musuem Algorithm is?
a event where solutions can be generated randomly but solution is not guaranteed. unacceptable amount of time of process.
What is steepest-ascent hill climbing?
developed from simple hill climbing. All successors of a node are evaluated and the one that give the most improvement is selected.
Problems In Hill-Climbing?
- Local Maxima or Local Minima
Unless the heuristic is convex, it may not reach a global maximum. - Ridges
Ridges is a curve in the search place that leads to a maximum, but the orientation of the ridge compared to the available moves that are used to climb is such that each move will lead to a smaller point. - Pleteau
Pleteau is encountered when the search space is flat, or sufficiently flat that the value returned by the target function is indistinguishable from the value returned for nearby regions due to the precision used by the machine to represent its value.
solutions to hill climbing problems?
- Backtrack to some earlier node and try going in a different location
- Make a big jump to try to get in a new section
- Moving in several directions at once
What is Simulated Annealing?
Simulated annealing (SA) is a method for solving unconstrained and bound-constrained optimization problems. From the current state, pick a random successor state.
Minimax Algorithm steps?
- Generate game tree completely
- Determine utility of each terminal state
- Propagate the utility values upward in the tree by applying MIN and MAX operators on the nodes in the current level
- At the root node use minimax decision to select the move with the max (of the min) utility value
Minimax algorithm characteristics?
Complete? YES
Optimal? YES
Time Complexity? O(b^m)
Space Complexity? O(b.m)
Alpha-Beta pruning?
alpha = MAX
beta = MIN
the basic idea of alpha-beta pruning is to prune portions of the search tree that cannot improve the utility value of the max or min node, by just considering the values of nodes seen so far.
