Production Systems

1.1 Introduction to AI

Introduction

Many human mental activities such as developing computer programs, working out mathematics, engaging in common sense reasoning, understanding languages and interpreting it, even driving an automobile are said to demand "intelligence". Several computer systems have been built that can perform tasks such as these. Also there are specially developed computers systems that can diagnose disease, solve quadratic equations, understand human speech and natural language text.

We can say that all such systems possess certain degree of artificial intelligence. The central point of all such activities and systems is that "How to think" OR rather "How to make system think". The process of thinking has various steps like perceive, understand, predict and manipulate a world that is made up of tiny complex things or situations.

The field of AI not just attempts to understand but also it builds intelligent entities.

Various Definitions of AI

AI may be defined as the branch of computer science that is concerned with the automation of intelligent behaviour. (Luger - 1993) v Systems that thinks like human. v The exciting new effort to make computers think ... machines with minds, in the full and literal sense. (Hallgeland - 1985) v "The automation of activities that we associate with human thinking, activities such as decision making, problem solving, learning ..." (Bellman - 1978) v Systems that act like humans. v "The art of creating machines that perform functions that require intelligence, when performed by people". (Kurzweil - 1990) v "The study of how to make computers do things at which, at the moment, people are better". (Rich and Knight - 1991).

Systems that think rationally. v The study of mental faculties through the use of computational models. (Charniak and McDermott - 1985) v "The study of the computations that make it possible to perceive, reason and act". (Winston - 1992) v Systems that act rationally. v "Computational intelligence is the study of the design of intelligent agents". (Poole et al - 1998) v "AI is concerned with intelligent behaviour in artifacts". (Nilsson - 1998) These definitions vary along two main dimensions. First dimension is the thought process and reasoning and second dimension is the behaviour of the machineThe first seven definitions are based on comparisons to human performance where as remaining definitions measure success against an ideal concept of intelligence, which we call rationality. A system is rational if it does the "right thing" given what it knows. Historically, there are four approaches that are followed in AI. These four approaches are Acting Humanly, Thinking Humanly, Thinking Rationally and Acting Rationally.

Let us consider four approaches in detail.

1. Acting Humanly Tuning test

For testing intelligence Alan Turing (1950) proposed a test called as Turing test. He suggested a test based on common features that can match with the most intelligent entity-human beings.

Computer would need to possess following capabilities:

Natural language processing-To enable it to communicate successfully in English.

Knowledge representation to store what it knows, what it hears.

Automated reasoning to make use of stored information to answer questions being asked and to draw conclusions.

Machine learning to adapt to new circumstances and to detect and make new predictions by finding patterns.

Turing also suggested to have physical interaction between interrogater and computers. Turing test avoids this but Total Turing Test includes video signal so that the interrogator can test the subject's perceptual abilities, as well as the opportunity for the interrogator to pass the physical objects "through the hatch".

To pass total turing test in addition, computer will need following capabilities.

v Computer vision to perceive objects.

v Robotics to manipulate objects.

2. Thinking Humanly

As we are saying that the given program thinks like human it we should know that how human thinks. For that, the theory of human minds needs to be explored. There are two ways to do this: through introspection i.e. trying to catch our own thoughts as they go by and through psychological experiments.

If computer programs, I/O and timing behaviours matches corresponding human behaviours, that is, we can say that some of the program's mechanisms could also be operating in human. The interdesciplinary field of cognitive science brings together computer models from AI and experimental techniques from psychology that try to construct precise and testable theories of the workings of human mind.

3. Thinking Rationally-the "laws of thought approach"

The concept of "Right thinking" was proposed by Aristotle. This idea provided patterns for argument structures that always yielded correct conclusions when given correct premises.

For example,

"Ram is man", "All men are mortal", "Ram is mortal".

These laws of thought were supposed to govern the operation in the mind; their study initiated the field called logic which can be implemented to create intelligent systems.

4) Acting Rationally

An agent (Latin agre-to do) is something that acts. But computer agents are expected to have more other attributes that distinguish them from just the "programs", because they need to operate under autonomous control, perceiving their environment, persisting over a prolonged time period, adapting to change and being capable of taking on another goals. A rational agent is expected to act so as to achieve the best outcome or when there is uncertainity to achieve best expected outcome.

The laws of thought emphasis on correct inference which should be incorported in rational agent.

The AI Foundation

Now we discuss the various disciplines that contributed ideas, viewpoints and techniques to AI.

Philosophy provides base to AI by providing theories of relationship between physical brain and mental mind, rules for drawing valid conclusions. It also provides information about knowledge origins and the knowledge leads to action.

Mathematics gives strong base to AI to develop concrete and formal rules for drawing valid conclusions, various methods for date computation and techniques to deal with uncertain information.

Economics support AI to make decisions so as to maximize payoff and make decisions under uncertain circumstances.

Neuroscience gives information which is related to brain processing which helps AI to develope date processing theories.

Phychology provides strong concepts of how humans and animals think and act which helps AI for developing process of thinking and actions.

The Strong and Weak AI

After taking brief look at various disciplines that contribute towards AI, now let us look at the concept of strong and weak AI which also gives basic foundation for developing automated systems.

Strong AI

This concept was put forward by John Searle in 1980 in his article, "Minds, Brains and Programs". Strong form AI provides theories for developing some form of computer based AI that can truly reason and solve problems. A strong form of AI is said to be sentient or self- aware.

Strong AI can be categorized as,

Human-like AI-In which the computer program thinks and reasons much like a human-mind.

Non-human-like AI-In which the computer program develops a totally non-human sentience, and a non-human way of thinking and reasoning.

Weak AI

Weak artificial intelligence research deals with the creation of some form of computer based AI that cannot truly reason and solve problems. They can reason and solve problems only in a limited domain. Such a machine would, in some ways, act as if it were intelligent, but it would not possess true intelligence.

There are several fields of weak AI, one of which is natural language. Much of the work in this field has been done with computer simulations of intelligence based on predefined sets of rules. Very little progress has been made in strong AI. Depending on how one defines one's goals, a moderate amount of progress has been made in weak AI.

The History of AI

The early work that is now generally recognized as AI was done in the period of 1943 to

1955. The first AI thoughts were formally put by men McCulloch and Walter Pitts (1943). Their idea of AI was based on three theories, firstly basic phsycology (the function of neurons in the brain), secondly formal analysis of propositional logic and third was Turing's theory of computation. Later Donald Hebb in 1949 demonstrated simple updating rule for modifying the connection strengths between neurons. His rule now called Hebbian learning which is considered to be great influencial model in AI. There were huge early day work that can be recognized as AI but Alan Turing who first articulated a complete vision of AI in his 1950 article named "Computing Machinery and Intelligence". Real AI birth year is 1956 where in John McCarthy held workshop on automata theory, neural nets and study of intelligence where other researchers also presented their papers and they come out with new field in computer science called AI. From 1952 to 1969 large amount of work was done with great success. Newell and Simon's presented General Problem Solver (GPS) within the limited class of puzzles it could handle. It turned out that the order in which the program considered subgoals and possible actions was similar that in which humans approached the same problems. GPS was probably the first program which has "thinking humanly" approach. Herbert Gelernter (1959) constructed the Geometry Theorem Prover which was capable of proving quite tricky mathematics theorem. At MIT, in 1958 John McCarthy made major contributions to AI field: development of HLL LISP which has became the dominant AI programing language. In 1958, McCarthy published a paper entitled Programs with Common Sense, in which he described the Advice Taker, a hypothetical program that can be seen as the first complete AI

system. Like the Logic Theorist and Geometry Theorem Prover. McCarthy's program was designed to use knowledge to search for solutions of problems.

The program was also designed so that it could accept new axioms in the normal course of operation, thereby allowing it to achieve competence in new areas without being reprogrammed. The Advice Taker thus embodied the central principles of knowledge representation and reasoning.

Early work building on the neural networks of McCulloch and Pitts also flourished. The work of Winogard and Cowan (1963) showed how a large number of elements could collectively represent an individual concept, with a corresponding increase in robustness and parallelism. Hebb's learning methods were enhanced by Bernie Widrow (Widrow and Hoff, 1960; Widro,

1962), who called his networks adalines, and by Frank Rosenblatt (1962) with his perceptrons. Rosenblatt proved the perceptron convergence theorem, showing that his learning algorithm could adjust the connection strengths of a perception to match any input data, provided such a match existed. In 1965, Weizenbaum's ELIZA program appeared to conduct a serious conversation on any topic by basically borrowing and manipulating the sentences given by a human. None of the programs developed so far, had complex domain knowledge and were called 'weak' methods. Researchers realized that it was necessary to use more knowledge for more complicated, larger reasoning tasks. The DENDRAL program was developed by Buchanan in 1969 and was based on these principles. It was a unique program that effectively used domain specific knowledge in problem solving. In the mid-1970's, MYCIN, a program developed to diagnose blood infections. It used expert knowledge to diagnose illnesses and prescribe treatments. This program is also known as the first program, which addressed the problem of reasoning with uncertain or incomplete information. Within a very short time a number of knowledge representation languages were developed such as predicate calculus, semantic networks, frames and objects. Some of them are based on mathematical logic such as PROLOG. Although PROLOG goes back to 1972, it did not attract wide spread attention until a more efficient version was introduced in 1979. As the real, useful strong works on AI were put forward by researchers, AI emerged to be a big Industry. In 1981, Japanese announced 5^th generation project a 10 -year plan to build intelligent computers running PROLOG. US also formed the Micro-electronics and Computer Technology Corporation (MCC) for research in AI. Overall the AI industry boomed from few million dollars in 1980 to billions of dollars in 1988. But soon after that AI industry had huge setback as many companies suffered as they failed to deliver on extra vagant promises.

In late 1970s more research were done by psychologists on neural networks which continued in 1980s.

In 1990s AI emerged as a science. In terms of methodology AI has finally come firmly under the scientific method. In recent years approaches based on Hidden Markov Models (HMMS) have come to dominate the AI field. This model is based on two aspects one is rigorous mathematical model theory and second is, these models are generated by a process of training on a large corpus real speech data.

Judea Pearl's (1988) Probabilistic Reasoning in Intelligent Systems led to a new acceptance of probability theory in AI. Later Bayesian network was invented which can represent uncertain knowledge along with reasoning support.

Judea Pearl, Eric Hovitz and David Hackerman in 1986 promoted the idea of normative expert systems that can act rationally according to the laws of decision theory.

Similar but slow revolution have occurred in robotics, computer vision and knowledge representation.

In 1987 a complete agent architecture called SOAR was work out by Allan Newell, John Laired and Paul Rosenbloom. Many such agents were developed to work in big environment "Internet". AI systems have become so common in web based applications that the "- bot" suffix has entered in everyday language.

AI technologies underlie many Internet tools, such as search engines, recommender systems and website.

While developing complete agents it was realized that previously isolated subfields of AI need to reorganize when their results are to be tied together.

Today, In particular it is widely appreciated that sensory systems (vision, sonar, speech-recognition, etc.) cannot deliver perfectly reliable information about the environment. Hence reasoning and planning systems must be able to handle uncertainity. AI has been draw in to much closer contact with other fields such as control theory and economics, that also deal with agents.

What AI can do Today ?

Autonomous Planning and Scheduling

NASA's Remote Agent program became the first on-board autonomous planning program to control the scheduling of operations for spacecraft. Such remote agents can do task of detecting, diagnosing and recovering from problems as they occurred.

Game Playing

A computer chess program by IBM named as Deep Blue defeated world chess champion Garry Kasparov in exhibition match in 1997. Such type of gaming programs can be developed using AI techniques.

Autonomous Control

The ALVINN computer vision system was trained to stear car to keep it following a lane. It was made to travel 2850 miles in which 98% of the time control was with the system and only 2% of the time human took over. AI can give more theories to develop such systems.

Diagnosis

Heckerman (1991) describes a case where a leading expert on lymph node pathology scoffs at a program's diagnosis of an difficult case. The machine can explain the diagnosis. The machine points out the major factors influencing its decision and explain interaction of several of the symptoms in this case. If such diagnostic programs are developed using AI then highly accurate diagnosis can be made.

Logistic Planning

In 1991 during the persion Gulf Crisis U.S. forces deployed a dynamic analysis and replanning tool name DART for automated logistics planning and scheduling for transportation.

Robotics

For doing complex and critical tasks systems can be developed using AI techniques. For e.g. Surgeons can use robot assistants in microsurgery which can generate 3D vision of patients internal anatomy.

Language Understanding and Problem Solving

PROVERB is computer program which expert in solving crossword puzzles. It can make use of constraints or possible word fillers, a large database of past puzzles and variety of information sources including dictionaries and online databases. Such as a list of movies and the actors that appears in them.

AI does not generate magic or science fiction but rather it can develops science, engineering and mathematics system.

Recent progress in understanding the theoretical basis for intelligence has gone hand in hand with improvements in the capabilities of real systems. The subfields of AI have became more integrated and AI has found common ground with other disciplines.

1.2 Formulation and Definition of the Problem

What is Problem Solving?

For solving any type problem (task) in real world one needs formal description of the problem.

One should have clear understanding of following aspects of the problem,

1. What is the Explicit Goal of the Problem

Goals help to organize behaviour of systems by limiting the objectives that the agent is trying to achieve. Goal formulation is based on the current situation and the agent's performance measure. It is first step towards problem solving.

2. What is Implicit Criteria for Success

That is how success is defined. That will be the ultimate thing system needs to achieve, which is the problem solution's output.

3. What is the Initial Situation

It means that what is going to be the start state of problem being solved.

4. Ability to Perform

It tells how agents transforms from one situation to another, how operations and rules are specified which change the states of the problem during solution process.

Well Defined Problems

Problem formulation is the process of deciding what actions and states to consider, given a goal.

A problem can be defined formally by four components.

1. Initial state that the agent starts in For example

Consider an agent program Indian Traveller developed for travelling from Pune to Chennai travelling through different states. The initial state for this agent can be described as In (Pune).

Fig. 1.1 Indian traveller map.

2. A description of the possible actions available to the agent

The most common formulation uses a successor function. Given a particular state x, SUCCESSOR Function (𝑋) returns a set of <action, successor>, ordered pairs, where each action is one of the legal actions in state 𝑥 and each successor is a state that can be reached from 𝑥 by applying the action.

For example

From the state In (Pune), the successor function for Indian Traveller problem would return.

{ < Go (Mumbai), In (Mumbai) >

< Go (AhemdNagar), In (AhemdNagar)>

< Go (Solapur), In (Solapur)>

< Go (Satara), In (Satara)>

}

Together, the initial state and successor function implicitly define the state space of the problem-which is the set of all states reachable from the initial state.

The state space forms a graph in which the nodes are states and the arcs between nodes are actions.

A path is the state space is a sequence of states connected by a sequence of actions.

3. The goal test, which determines whether a given state is goal (final) state. In some problems we can explicitly specify a set of goals. If a particular state is reached we can check it with set of goals and if a match is found success can be announced. For example In Indian Traveller problem the goal is to reach chennai i.e. it is a singleton set {In (Chennai) }. In certain types of problems we can not specify goals explicitly. Instead, goal is specified by an abstract property rather than an explicitly enumerated set of states.

For example

In chess, the goal is to reach a state called "Checkmate" where the opponent's king is under attack and can’t escape. This "Checkmate" situation can be represented using various state spaces.

4. A path cost function that assigns a numeric cost (value) to each path. The problem-solving agent is expected to choose a cost-function that reflects its own performance measure. For Indian-Traveller agent we can have time required as cost for path-cost function. It should consider length of each road being travelled. In general step-cost of taking action ' a ' to go from state x to state y is denoted by 𝑐(𝑥, 𝑎, 𝑦). The above 4 elements define a problem and can be put together in single data structure which can be given as input to a problem-solving algorithm. A solution to the problem is a path from the initial state to a goal state. We can measure quality of solution by the path cost function. We can have multiple solutions

to the problem. The optimal solution will be the one with lowest path cost among all the solutions.

Problem Formulation Types

There are two main kinds of problem formulation,

1. Incremental formulation
2. Complete-state formulation. Depending upon problem requirements and specification one can decide which one to go for.

Incremental formulation

It involves operators that augment the state description, starting with an empty state. v It generates many sequences. v Memory requirements is less as all states are not explored (exploration will be done till the goal is found). For example For the 8-queens problem, incremental formulation states that, each action adds a queen to the state. In this formulation we have 64.63 … 57 ≈ 3 × 10¹⁴ possible sequences to investigate. Complete state formulation v In this initially we will have some basic configuration represented in initial state. v Here while doing any action first the conditions on the actions will be checked so that the configuration state after the action will be same legal state. v It takes up large memory as complete state space is generated. This formulation reduces number of sequences generated. For example In 8-queen problem initially all the queens will be arranged on the board. The action will be 'move a queen to the next square such that it is not attacking'. This complete state formulation reduces state space from 3 × 10¹⁴ (which is for incremental formulation) to just 2,057 and solutions are easy to find.

Example of incremental formulation and complete-state formulation

Consider 8-queen problem,

Incremental formulation

1. States v Arrangement of upto 8 queens on the board.

2. Initial state v Empty board.

3. Successor function (operators) v Add a queen to any square.

4. Goal test v All queens on board v No queen attacked. Properties: 3 × 10¹⁴ possible sequences.

Complete state formulation

1. States v Arrangement of 8-queens on the board.
2. Initial state v All 8 queens on board.
3. Successor function (operators) v Move a queen to a different square.
4. Goal test v No queen attacked. Properties: Good strategies can reduce the number of possible sequences which are considerable.

Solving the Problem

Finding the solution of a problem is procedure which involves following phases,

1. Problem definition: Wherein detailed specification of inputs and what constitutes an acceptable solution is described.
2. Problem analysis: Wherein problem is studied through various view points like inputs, to the problem, environment of the problem, expected outputs.
3. Knowledge representation: Wherein the known data about the problem and various expected stimuli from environment is represented in particular format which is helpful for taking actions.
4. Problem solving: Wherein the selection of best suited techniques for problem solutions are thought of and finalized.

Problem Solving Agents Approach of Problem Solving Agent

Fig. 1.2 Steps in problem solving.

Goal based agents are also called as problem solving agent.

Problem solving agent adapt to the task environment understand goal and achieve success

Problem solving agents determine sequence of actions which generate successful state.

Problem solving agent can be aimed at maximizing performance measure there by developing intelligent problem solving agent.

Steps in Problem Solving

Problem solving agent achieves success by taking following approach to problem solution,

Step 1: Goal setting

Agent set the goal by considering the environment.

Step 2: Goal formulation

The goals set in step 1 are formalized in the frame work. The key activity in goal formulation is

1. To observe current state.
2. To tabulate agents performance measures.

Step 3: Problem formulation

After formulating goal, it is required to find out what will be the sequence of actions which generate goal state.

Problem formulation is a way of looking at actions and states generated because of actions, which leads to success.

Step 4: Search in unknown environment

If the task environment is unknown then agent first tries different sequence of actions and gathers knowledge (i.e. learning). Then agent gets known set of actions which leads to goal state. Thus agent search for describable sequence of actions this process is called as searching process.

With knowledge of environment and goal state we can design a search algorithm. A search algorithm is a procedure which takes problem as input and return its solution which represented in the form of action sequence.

Step 5: Execution phase

Once the solution is given by the search algorithm then the actions suggested by the algorithm are executed. This is the execution phase. Solution guides agent for doing the actions. After executing the actions agent again formulate new goal.

Fig. 1.3 Problem solving agent.

Algorithm

Procedure or method: Problem solving agent (unknown space, percept). Results: An action. Input: P → percept (Environment perception) Static:

1. A → An action sequence, initially with null value.

2. S → State-current state.

3. G → Goal-A goal initially null.

4. P → Problem-A real world situation. State-update state (State, percept) If ( s ) is empty then do

Example problems

1. General Route Finding Problem

Problem Statement: Route-finding problem is defined in terms of specified locations and transitions along links between them. Route-finding algorithms are used in a variety of applications, such as routing in computer networks, military operations planning, and air line travel planning systems.

1. States: Locations
2. Initial state: Starting point
3. Successor function (operators): Move from one location to another.
4. Goal test: Arrive at a certain location.
5. Path cost: May be quite complex, which can involve factors like, Money, time, travel, comfort, scenery, ... etc.

Simplified Example of Route Finding Problem [Airline Travelling Problem]

Problem Statement: Starting from initial location one has to reach at the specified destination by some prespecified time.

1. States: Each state is represented by a location (e.g. an airport) and the current time.

2. Initial state: This is specified by the problem.

3. Successor function: This returns the states resulting from taking any scheduled flight (perhaps further specified by seat class and location), leaving later than the current time plus the time within-airport transit time, from the current airport to another.

4. Goal test: Are we at the destination by some prespecified time ?

5. Path cost: This depends on monetary cost, waiting time, flight time, customs and immignation procedures, seat quality, time of day, type of airplane, frequent-flyer mileage awards, and so on.

2. VLSI Layout Problem

Problem Statement: A VLSI layout problem requires positioning millions of components and connections on a chip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize manufacturing yield.

1. States

Positions of components, wires on a chip.

2. Initial state v Incremental: No component placed. v Complete-state: All components place (e.g. randomly, manually).

3. Successor function (operators)

Incremental: Place components, route wire. v Complete-state: Move component, move wire.

4. Goal test v All components placed. v Components connected as specified.

5. Path cost

May be complex. One can consider distance, capacity, number of connections per component, for path cost computation.

Detail description of VLSI layout problem

When logical design is made, the layout problem come and the problem is divided into two parts

1. Cell layout 2) Channel routing as below,

1. Cell layout

The basic components of circuit are grouped into cells, each cells perform some recognition. The cells of standard size are connected to each of the other cell. v The overlapping between the cell component is avoided. Some sort of room is provided for connecting wires.

2. Channel routing

The cell components are fixed on a chip. v The channel routing task is to search a particular route for each wire. The functional task is achieved through the gaps between the cells. v The complex algorithm are designed to perform the channel routing. The degree of complexity is so high, but it is always possible to solve problem with specific algorithm.

1.3 System of Production

Since, search forms the core of many intelligent processes, production system is useful to structure AI programs in a way that facilitates describing and performing the search process.

Production systems provide such structures. If one adopts a system with production rules and a 'rule interpreter' then the system is known as a 'production system'. or "One convenient representational form of an action function is a production system".

A production system is a model of computation that provides pattern-directed search control using a set of production rules, a working memory, and a recognize-act cycle.

The productions are rules of the form 𝐂 → 𝐀, where the LHS is known as the condition and the RHS is known as the action. These rules are interpreted as follows: given condition, 𝐶, take action 𝐴. The action part can be any step in the problem solving process. The condition is the pattern that determines whether the rule applies or not. v There is a set of rules, each consisting of a left side (a pattern) that determines the applicability of the rule and a right side that describes the operation to be performed, if the rule is applied. These rules are called production rules or simply productions. Each rule is written in the form 𝑐_𝑖 → 𝑎_𝑖, where 𝑐_𝑖 is the condition part and a_i is the action part. v A production system consists of a list of such rules-c₁ → a₁ c₂ → a₂ ∶ c_i → a_i ∶ c_m → a_m

In general the condition part of a rule can be any binary-valued ( 0,1 ) function of the features resulting from perceptual processing of line sensory inputs. Often, it is a monomial-a conjunction of Boolean literals. To select an action, the rules are processed as follows,

1. Starting with the first rule, namely 𝑐₁ → 𝑎₁; we look for the first rule is the ordering whose condition part evaluates to 1 and select the action part of that rule. The action part can either be primitive action, a called to another production system, or a set of action to be executed simultaneously.
2. One or more knowledge/database that contain whatever information is appropriate for the particular task. Some parts of the database may be permanent, while other parts of it may pertain only to the solution of the current problem. The information in these databases may be structured in any appropriate way.
3. A control strategy that specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once.
4. A rule applier-One major issue to be solved in a production system is 'conflict resolution'. Conflict resolution arises when there are more than one rule that can be fired in a situation and the rule interpreter is to decide which is to be fired, what is the order of triggering and whether to apply all that are applicable or to be only selective.

Following are a few strategies by which conflicts can be resolved.

These are termed as conflict resolution strategies. Some of the conflict resolution strategies are,

i) Perform the first- In this method, the system chooses the first rule that matches. ii) Sequencing techniques- Adopt the rules in the sequence they are. **iii) Perform the most specific -**If there are two matching rules and one is more specific than the other, activates the most specific rule. **iv)Most recent policy -**It is generally believed that a newly added rule is more knowledgeable than existing ones. Hence, if a system is adopting this method, it should fire the most recent rule. However, there is slight overhead associated with this strategy in that the system has to keep track of which rule came in at what time, which rules were modified etc. v Working memory contains a description of the current state of the world in the problem-solving process. The description is matched against the conditions of the production rules. When a conditions matches, its action is performed. Actions are designed to alter the contents of working memory. v The recognize-act cycle is the control structure. The patterns contained in working memory are matched against the conditions of the production rules, which produces a subset of rules known as the conflict set, whose conditions match the contents of working memory. One (or more) of the rules in the conflict set is selected (conflict

resolution) and fired, which means its action is performed. The process terminates when no rules match the contents of working memory.

Background

Post (1943) proposed the production rule model as a formal theory of computation. It is equivalent in power to a Turing machine. v Newell and Simon (1960s) system, General Problem Solver used production system as a model of human cognition. Production rules represent problem-solving skills stored in a person's long-term memory. The working memory represents the person's current focus of attention. Choosing rules to apply, occurs through unconscious pattern matching. v Production systems have been developed for a wide variety of problems, ranging from algebra word problems, mathematical and logical proofs, physics problems and games. v John Anderson (1983) proposed a production system known as ACT* as a model of human cognition and learning. v Newell, Rosenbloom and Laird (1990) proposed a production system known as SOAR (Symbols, Operators AND Rules) as a model of human cognition and learning. v The OPS (Official Production System) languages are based on the production system model. v 1980s : Production systems were the basis of rule-based expert systems. v Production system is model for Human Problem Solving (SOAR, ACT*)

Purpose of Production System and Various Types of Production Systems

Production system is a good way to describe the operations that can be performed in a search for a solution to a problem.

Production systems like problems can be described by a set of characteristics that shed some light on how they can easily be implemented?

As we have following classes of production systems,

1. A monotonic production system
2. A non-monotonic production system
3. A partially commutative production system
4. A commutative production system

A monotonic production system: It is a production system in which the application of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was selected. A non-monotonic production system: It is a production system in which the application of a rule prevents the later application of another rule that could also have been applied at the time the first rule was selected. A partially commutative production system: This system states that if the application of a particular sequence of rules transforms state x into state y, then any permutation of those rules that is allowable also transforms state x into state 𝑦. A commutative production system: It is a production system that is both monotonic and partially commutative. There exist an infinite number of production systems that describes ways to find solutions. For any solvable problem i.e., any problem can be solved by any production system. Or generally we cannot define a relationship between kinds of production and kinds of production system. Since, all problems can be solved by all kinds of systems.

Table. 1.1 shows four categories of production systems.

Table. 1.1 The four categories of production systems.

Partially commutative, monotonic production systems are useful for solving ignorable problems as shown in left upper corner. Ignorable problems are one for which a natural formulation leads to solution steps that can be ignored. Such a natural formulation will then be a partially commutative, monotonic system. These problems have some creative processes and ignore changing old ones. Theorem proving is one of the example of such a creative process. These systems are useful from implementation standpoint as it can be implemented without the ability to backtrack to previous states when it is discovered that an incorrect path has been followed.

Non-monotonic, partially commutative systems are useful for the problems in which changes occur but can be reversed and in which order of operations is not critical.

This is usually the case in physical manipulation problems, such as robot navigation on a flat plane.

Consider following operators: N-to move north E-to move east

W-to move west S-to move south. To reach its goal, it does not matter whether the robot executes N − N − E or N − E − N depending on how the operators are chosen.

8 -puzzle and block world problems are also of same kind problem. Not partial commutative are useful for many problems in which irreversible changes occur. For example, for making a particular chemical compound, there is fixed process for it. Say a chemical has to be added to B at certain temperature then C chemical should be added to mixture to get the required compound. This would not be possible if we add C to A first then B to it. So, in this type of processes order is very important i.e., make correct decision the first time. In this system, it is less likely to produce the same node many times in the search process.

Advantages and Disadvantages of Production System

Advantages of Production Systems

Production systems provide an excellent tool for structuring AI programs. v Production systems are highly modular because the individual rules can be added, removed or modified independently. v The production rules are expressed in a natural form, so the statements contained in the knowledge base should be the recording of an expert thinking out loud.

Disadvantage of Production Systems

One important disadvantage is the fact that it may be very difficult to analyse the flow of control within a production system because the individual rules don't call each other.

Search Control in Production System

Data driven (C → A): If C matches, then perform A, changing WM. v Goal driven (C → A): If A matches a goal in WM, then add C (subgoal) to WM. v The order of the rules or clauses affects search control. v Heuristic knowledge can be built into the rules. v Conflict resolution: refraction-If rule C → A has fired, don't refire it until the conditions, C, have changed in WM. (prevents looping) v Conflict resolution recency-fire rules whose conditions match the newer additions to WM. (Focused reasoning) v Conflict resolution: specificity-prefer rules that have more conditions and hence match with fewer WM patterns.

Important Characteristics of Production System Model

There is separation of knowledge (the rules) and control (recognize-act cycle) in the system. v Natural mapping onto state space search (data or goal driven) is done. v There is modularity of production rules (rules represent chunks of knowledge). v Pattern-directed control (more flexible than algorithmic control) is done in the system. v Opportunities for heuristic control can be built into the rules. v Tracing and explanation (Simple control, informative rules) is possible in the system. v The systems are language independent. v It has been used as model for human problem solving (SOAR, ACT^∗).

1.4 Methods of Search

At every stage in state space generating algorithms we need to apply searching procedure so as to reach to goal state. Search is a systematic examination at states to find path from the root state (initial state) to the goal state. The output of this procedure is the solution (goal) state.

There are 2 Basic Types of Search Strategies

1. Uninformed search (Blind search)

They have no additional information about states other than provided in the problem definition. They can only generate successors and distinguish between goal state and non-goal state.

2. Informed search (Heuristic search)

This can decide whether one non-goal state is more promising than another non-goal state.

Key Point: All the search strategies are distinguished by the order in which the nodes are expanded.

Uninformed Search Strategies

B.F.S. v D.F.S. v Depth limited search v Iterative deepening DFS

Bidirectional search v Uniform cost search In the following section we will discuss each uninformed searching in detail. For each searching technique we will see its basic methodology, its algorithmic implementation and its performance evaluation. Performance evaluation will be done on the basis of 4 criteria’s we have seen previously namely,

1. Completeness
2. Optimality
3. Time complexity
4. Space complexity. Generally it does happen that space and time complexity depends on some factors hence we will discuss them combinely.

Breadth-First Search

The procedure: In BFS root node is expanded first, then all the successor of root node are expanded and then their successor and so on. That is the nodes are expanded level wise starting at root level.

The implementation: BFS can be implemented using first, in first out queue data structure where fringe will be stored and processed. As soon as node is visited it is added to queue. All newly generated nodes are added to the end of the queue, which means that shallow nodes are expanded before deeper nodes.

The performance evaluation

1. Completeness: BFS is complete because if the shallowest goal node is at some finite depth d, BFS will eventually find it and will generate solution. (assuming that branching factor 𝑏 is finite).
2. Optimality: The shallowest goal node is not necessarily optimal. BFS will yield optimal solution only when all actions have the same cost, let it be at any depth.
3. Time and space complexity: As the level of search tree grows more time is incurred. In general if search tree is at level 𝑑 then 𝑂(𝑏^𝑑+1) time is required, where 𝑏 is the number of nodes generated from each node, starting at root node i.e. root generates b nodes and each b node generates b more and so on shown below.

Every node generated should remain in memory till its exploration. If branching factor ' b ' is more then more memory will be required.

For example

If branching factor b = 10 at some level d = 6. If we assume 10,000 nodes will be generated per second and per node 1000 bytes are required for storage.

Then total generated nodes = 10⁷ which will take 19 minutes but it will take 10 Gigabytes for storing them.

We can conclude that for BFS space complexity is major issue concerned than time complexity. Time complexity is critical issue when depth of tree increases.

Key Point: We can use uninformed methods for exponential-complexity search only when problems have smallest instances.

Algorithm BFS (G, n)

//Breadth first search of G

{

for i := 1 to n do // Mark all vertices unvisited

visited [i]:=O;

for i:= 1 to n do

if (visited [i] = o) then BFS (i);

}

BFS

v Time complexity-O(b^d+1)

v Space complexity - 𝑂(𝑏^𝑑+1)

BFS

D and J are goal state. [D is found through the path] → (A-B-D) (shallowest goal)

Fig. 1.4 Breadth-first search.

Note: The numeric value beside each node indicates the order in which nodes are visited

(reached).

Uniform Cost Search

The procedure: Uniform cost search expands the node ' 𝑛 ' with the lowest path cost. Uniform cost search does not care about the number of steps a path has, instead it considers their total cost. Therefore, their is a chance of getting stuck in an infinite loop if it ever expands a node that has a zero-cost action leading back to the same state.

The implementation: We can use queue data structure for storing fringe as in BFS. The major difference will be while adding the node to queue, we will give priority to the node with lowest path cost. (So the data structure will be a priority queue).

The performance evaluation

1. Completeness: Uniform cost search guarantees completeness provided the cost of every step is greater than or equal to some small positive constant " c ".
2. Optimality: If cost of every step is greater than or equal to some small positive constant then uniform cost search will yeild optimal solution, by reaching the goal state which has lowest path cost.
3. Time and space complexity: Uniform-cost search does not care about the number of steps a path has, but only about their total cost. Therefore, it will get stuck in an infinite loop if it ever expands a node that has a zero-cost action leading back to the same state. Uniform-cost search is guided by path costs rather than depths, so its complexity cannot easily be characterized in terms of 𝑏 and 𝑑. Instead, let 𝐶^∗ be the cost of the optimal solution, and assume that every action costs at least E. Then the algorithm's worst-case time and space ^[𝐶 ∗ /∈] complexity is 𝑂(𝑏), which can be much greater than 𝑏^𝑑.

Uniform cost search

Time complexity-O ( (Cl )

Space complexity-O ( (𝐶/𝜖 )

Where, C is the cost of optimal solution.

Fig. 1.5 Uniform cost search.

Assuming J and D are both goal state.

𝐴−𝐵−𝐸−𝐽

Note: The costs are associated with each edge.

Note: The numeric value beside each node indicates the order in which nodes are visited

(reached).

Depth-First Search

The procedure: Depth-first search always expands the deepest node in the current unexplored node set (fringe) of the search tree. The search goes in to depth until there is no more successor node. As these nodes are expanded, they are dropped from the fringe, so then the search "backs up" to the next shallowest node (previous level node) that still has unexplored successors.

The implementation: DFS can be implemented with stack (LIFO) data structure which will explore the latest added node first, suspending exploration of all previous nodes on the path. This can be done using recursive procedure that calls itself on each of the children in turn.

The performance evaluation

1. Completeness: As DFS explores all the nodes hence it guarantees the solution.

2. Optimality: As DFS reach to deepest node first, it may ignore some shallow node which can be goal state. Therefore optimality is expected only when all states have same path cost.

3. Time and space complexity: DFS requires some moderate amount of memory as it needs to store single path from root to some node to a particular level, along with unexpanded siblings. When same node gets fully explored, its complete branch (its all descendants and itself) will get removed from memory. With branching factor ' b ' and maximum depth d, dfs requires storage of-bd+1 nodes.

Algorithm DFS (v)

//Given an undirected (OR directed) graph G = (V, E) with

//n vertices and an array visited initially set

// to zero, this algorithm visits all vertices

//reachable from v. G and visited [] are global.

{

visited [v]:= 1;

for each vertex w adjacent from v do

{

if (visited [w] = 0 then DFS (w);

}

}

DFS [Depth First Search]

v Time complexity-O(b^d).

Space complexity −O(b^d + 1). Goal state path - (A-B - D) where D is a goal state.

Fig. 1.6 Depth First Search.

Note: The numeric value beside each node indicates the order in which nodes are visited

(reached).

A special case DFS → back tracking search: In this only one successor is generated at a time rather than all the successors and each partially expanded node remembers which successor to generate next.

This search technique uses less memory than DFS as only 'd' nodes (maximum depth) are required to store.