Resolution

resolution steps are applied  to CNFcomplete for FOL

 

Initial State: Knowledge base (KB) of axioms and negated theorem in CNF

Operators: Resolution rule picks 2 clauses and adds new clause

Goal Test: Does KB contain the empty clause?

Branches of AI and Applications of AI

 Branches of AI

 

logical AI

What a program knows about the world in general the facts of the specific situation in which it must act, and its goals are all represented by sentences of some mathematical logical language. The program decides what to do by inferring that certain actions are appropriate for achieving its goals.

search

AI programs often examine large numbers of possibilities, e.g. moves in a chess game or inferences by a theorem proving program. Discoveries are continually made about how to do this more efficiently in various domains.

pattern recognition

When a program makes observations of some kind, it is often programmed to compare what it sees with a pattern. For example, a vision program may try to match a pattern of eyes and a nose in a scene in order to find a face. More complex patterns, e.g. in a natural language text, in a chess position, or in the history of some event are also studied. These more complex patterns require quite different methods than do the simple patterns that have been studied the most.

representation

Facts about the world have to be represented in some way. Usually languages of mathematical logic are used.

inference

From some facts, others can be inferred. Mathematical logical deduction is adequate for some purposes, but new methods of non-monotonic inference have been added to logic since the 1970s. The simplest kind of non-monotonic reasoning is default reasoning in which a conclusion is to be inferred by default, but the conclusion can be withdrawn if there is evidence to the contrary. For example, when we hear of a bird, we man infer that it can fly, but this conclusion can be reversed when we hear that it is a penguin. It is the possibility that a conclusion may have to be withdrawn that constitutes the non-monotonic character of the reasoning. Ordinary logical reasoning is monotonic in that the set of conclusions that can the drawn from a set of premises is a monotonic increasing function of the premises. Circumscription is another form of non-monotonic reasoning.

common sense knowledge and reasoning

This is the area in which AI is farthest from human-level, in spite of the fact that it has been an active research area since the 1950s. While there has been considerable progress, e.g. in developing systems of non-monotonic reasoning and theories of action, yet more new ideas are needed.

learning from experience

Programs do that. The approaches to AI based on connectionism and neural nets specialize in that. There is also learning of laws expressed in logic.

planning

Planning programs start with general facts about the world (especially facts about the effects of actions), facts about the particular situation and a statement of a goal. From these, they generate a strategy for achieving the goal. In the most common cases, the strategy is just a sequence of actions.

epistemology

This is a study of the kinds of knowledge that are required for solving problems in the world.

ontology

Ontology is the study of the kinds of things that exist. In AI, the programs and sentences deal with various kinds of objects, and we study what these kinds are and what their basic properties are. Emphasis on ontology begins in the 1990s.

heuristics

A heuristic is a way of trying to discover something or an idea imbedded in a program. The term is used variously in AI. Heuristic functions are used in some approaches to search to measure how far a node in a search tree seems to be from a goal. Heuristic predicates that compare two nodes in a search tree to see if one is better than the other.

genetic programming

Genetic programming is a technique for getting programs to solve a task by mating random Lisp programs and selecting fittest in millions of generations. 

 

Applications of AI:

game playing

You can buy machines that can play master level chess for a few hundred dollars. There is some AI in them, but they play well against people mainly through brute force computation--looking at hundreds of thousands of positions. To beat a world champion by brute force and known reliable heuristics requires being able to look at 200 million positions per second.

speech recognition

In the 1990s, computer speech recognition reached a practical level for limited purposes. Thus United Airlines has replaced its keyboard tree for flight information by a system using speech recognition of flight numbers and city names. It is quite convenient. On the the other hand, while it is possible to instruct some computers using speech, most users have gone back to the keyboard and the mouse as still more convenient.

understanding natural language

Just getting a sequence of words into a computer is not enough. Parsing sentences is not enough either. The computer has to be provided with an understanding of the domain the text is about, and this is presently possible only for very limited domains.

computer vision

The world is composed of three-dimensional objects, but the inputs to the human eye and computers' TV cameras are two dimensional. Some useful programs can work solely in two dimensions, but full computer vision requires partial three-dimensional information that is not just a set of two-dimensional views. At present there are only limited ways of representing three-dimensional information directly, and they are not as good as what humans evidently use.

expert systems

A "knowledge engineer'' interviews experts in a certain domain and tries to embody their knowledge in a computer program for carrying out some task. How well this works depends on whether the intellectual mechanisms required for the task are within the present state of AI. When this turned out not to be so, there were many disappointing results. One of the first expert systems was MYCIN in 1974, which diagnosed bacterial infections of the blood and suggested treatments. It did better than medical students or practicing doctors, provided its limitations were observed. Namely, its ontology included bacteria, symptoms, and treatments and did not include patients, doctors, hospitals, death, recovery, and events occurring in time. Its interactions depended on a single patient being considered. Since the experts consulted by the knowledge engineers knew about patients, doctors, death, recovery, etc., it is clear that the knowledge engineers forced what the experts told them into a predetermined framework.

heuristic classification

One of the most feasible kinds of expert system given the present knowledge of AI is to put some information in one of a fixed set of categories using several sources of information.

Forward vs. backward chaining

Forward vs. backward chaining

•FC is data-driven, automatic, unconscious processing,

–e.g., object recognition, routine decisions

•May do lots of work that is irrelevant to the goal

•BC is goal-driven, appropriate for problem-solving,

–e.g., Where are my keys? How do I get into a PhD program?

•Complexity of BC can be much less than linear in size of KB

Inference

Inference: 

•KB ├i α = sentence α can be derived from KB by procedure i

•Soundness: i is sound if whenever KB ├i α, it is also true that KB╞ α

•Completeness: i is complete if whenever KB╞ α, it is also true.

 

•Preview: we will define a logic (first-order logic) which is expressive enough to say almost anything of interest, and for which there exists a sound and complete inference procedure.

•That is, the procedure will answer any question whose answer follows from what is known by the KB.

Logic

Logic:

•Logics are formal languages for representing information such that conclusions can be drawn

•S yntax defines the sentences in the language

•Semantics define the "meaning" of sentences;

 Entailment:

•Entailment means that one thing follows from another:

KB ╞ α

•Knowledge base KB entails sentence α if and only if α is true in all worlds where KB is true

»

–E.g., the KB containing “the Giants won” and “the Reds won” entails “Either the Giants won or the Reds won”

–E.g., x+y = 4 entails  4 = x+y

–Entailment is a relationship between sentences (i.e., syntax) that is based on semantics

Artificial Agent

Artificial Agent:

•Representation of knowledge and the reasoning process that brings knowledge to life.

•Knowledge and reasoning -artificial agent.

•Central component of the knowledge-based agent is its knowledge base or KB.

•Knowledge base = set of sentences.

•Language of sentence – Knowledge  representation language.

•Two standard tasks- TELL and ASK.

•Both task , involve – inference (deriving new sentence from old.

 

 

Backtracking search

•Variable assignments are commutative 

            [ WA = red then NT = green ] same as

            [ NT = green then WA = red ]

•Depth-first search for CSPs with single-variable assignments is called backtracking search.

•Chooses values for one variable at a time and backtracks when a variable has no legal value.

•Backtracking search is the basic uninformed algorithm for CSPs

Varieties of constraints

•Unary constraints involve a single variable,

–e.g., SA ≠ green

•Binary constraints involve pairs of variables,

–e.g., SA ≠ WA

•Higher-order constraints involve 3 or more variables

•Absolute constraint:

•Preference Constraint:

      Indicating which solution are preferred.

Varieties of CSPs

 Varieties of CSPs:

•Discrete variables

–finite domains:

–infinite domains:

•e.g., job scheduling, variables are start/end days for each job

•need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3

•Continuous variables

–e.g., start/end times for Hubble Space Telescope observations

Constraint satisfaction problems (CSPs)

•Standard search problem:

–state is a "black box“ – any data structure that supports successor function, heuristic function, and goal test

•CSP:

–state is defined by variables Xi with values from domain Di

–goal test is a set of constraints specifying allowable combinations of values for subsets of variables

•Simple example of a formal representation language

•Allows useful general-purpose algorithms with more power than standard search algorithms

Question bank

Memory bounded heuristic search

 Memory bounded heuristic search:

•To reduce memory- Iterative deepening to the heuristic search.

•2 memory bounded algorithm:

     1) RBFS (recursive best-first search).

     2) MA* (Memory-bounded A*) and 

         SMA*(simplified memory MA*)

RBFS:

 

•It attempts to mimic the operation of BFS.

•It replaces the f-value of each node along the path with the best f-value of its children.

•Suffers from using too little memory.

•Even if more memory were available , RBFS has no way to make use of it.

SMA*

 

•Proceeds life A*,expands best leaf until memory is full.

•Cannot add new node without dropping an old one. (always drops worst one)

•Expands the best leaf and deletes the worst leaf.

•If all have same f-value-selects same node for expansion and deletion.

•SMA* is complete if  any reachable solution.

Save water:

Espure Water Solution Pvt Ltd 

Chennai,India.

www.espure.in

Mobile: 9944116631 / 9841005335

Effluent Treatment Plant Manufacturer in Chennai

http://enpure.in/effluent-treatment-plant/

Informed search

 Informed search:

•That uses problem-specific knowledge beyond the definition of the problem itself.

•It can find solution more efficiently than uninformed search.

•Informed search – Best First Search.

Best-first search

•Idea: use an evaluation function f(n) for each node

Expand most desirable unexpanded node

•Implementation:

  Order the nodes in fringe in decreasing order of desirability

•Key component – heuristic function h(n)

     h(n) = estimated cost of the cheapest path from node n to goal node.

•Special cases:

–greedy best-first search

–A* search

Uninformed search strategies

•Uninformed search strategies use only the information available in the problem definition(Blind search)

•Breadth-first search

•Uniform-cost search

•Depth-first search

•Depth-limited search

•Iterative deepening search

Search strategies

•A search strategy is defined by picking the order of node expansion

•Strategies are evaluated along the following dimensions:

–completeness: does it always find a solution if one exists?

–time complexity: number of nodes generated

–space complexity: maximum number of nodes in memory

–optimality: does it always find a least-cost solution?

General tree search

Real world problem

Real world problem :

•Touring problem.

•Traveling sales man problem.

•VLSI. (component connections on chip, minimize-area, circuit delay, capacitance, maximize-manufacturing yield)

•Automatic assemble problem. (assemble the parts of some objects, protein design-to find sequence of amino acid)

•Internet searching. (looking for answer to questions)

 

Four components of a Well-defined problems

Four components

•Initial state.

•Successor function.

•Goal test.

•Path cost.

 

Initial state:

   The agent starts in.

Successor function:

   Given a state x,SUCCESSOR-FN(x)Returns a set of < action,successor> ordered pairs.

•The initial state and successor function define the state space.

 Goal test :

   Whether the given state is a goal state?

Path cost:

  Assigns numeric cost to each path.Step cost for taking action a from state x to y-denoted by c(x,a,y).

Solution:

  A path from initial to a goal state.

Solution quality:

   measured by cost.

Optimal solution:

   Lowest path cost among all solutions.

Save water:

Espure Water Solution Pvt Ltd 

Chennai,India.

www.espure.in

Mobile: 9944116631 / 9841005335

Effluent Treatment Plant Manufacturer in Chennai

http://enpure.in/effluent-treatment-plant/

Problem solving agent

•Goal formulation:

   Based on current situation and the agent’s performance measure-first step in problem solving.

•Problem formulation:

   Deciding what actions and state to consider, given a goal.

•An agent with several immediate options of unknown value can decide what to do by first examining different possible sequences of actions that lead to state of known value and then choosing the best sequence.-Search.

•Search algorithm-problem as input and returns the solution in the form of sequence.

•Solution found, action carried out-execution phase.

Learning agents

•It allows the agent to operate in unknown environment.

    4 components:

   1) Learning element.

   2) Performance element.

   3) Critic.

   4) Problem generator.

•Learning element:

    Responsible for making improvements.

•Performance element:

    Responsible for selecting external action. (entire agent)-Percepts and decides on action.

•Critic:

    Learning element uses feedback from critic-how the agent ids doing, how the performance element should be modified to do better in future. 
•Problem generator:

   Responsible for suggesting actions that will lead to new and informative experiences.

Agent types

 

Four basic types in order of increasing generality:

•Simple reflex agents

•Model-based reflex agents

•Goal-based agents

•Utility-based agents

Simple reflex agents:

•Select actions on the basis of the current percept, ignoring the rest of the percept histroy.

•Eg:

    Vacuum agent

• Its decision is based only on the current location and on whether that contains dirt

Model-based reflex agents:

•Partial observability-maintain some sort of internal state,depends on percept history,reflects some unobserved aspect.

    2 kind of knowledge:

 1)How world evolves independently of the agent.

2)How the agent’s own action affect the world.

“How the world works”-Model of the world

Goal-based agents:

            •With current state description, the agent needs goal information.

                 Eg: taxi driving- passenger’s destination.

             •Goal based action is straight forward.

                    “What will happen if I do such and such?”
Utility-based agents:

             •Goal alone are not enough to generate high quality

             •Goal just provide distinction between “happy” and “unhappy”.

                     Two kind of cases where goals are inadequate:

                          •  Conflicting goals-some of them can be achieved.

                          •Several goals-none can be acieved,importance of goals are taken.