(AI) The subfield of computer science concerned with the concepts and methods of symbolic inference by computer and symbolic knowledge representation for use in making inferences. AI can be seen as an attempt to model aspects of human thought on computers. It is also sometimes defined as trying to solve by computer any problem that a human can solve faster.
Examples of AI problems are computer vision (building a system that can understand images as well as a human) and natural language processing (building a system that can understand and speak a human language as well as a human). These may appear to be modular, but all attempts so far (1993) to solve them have foundered on the amount of context information and "intelligence" they seem to require.
The term is often used as a selling point, e.g. to describe programming that drives the behaviour of computer characters in a game. This is often no more intelligent than "Kill any humans you see; keep walking; avoid solid objects; duck if a human with a gun can see you"
1. The ability of a computer or other machine to perform those activities that are normally thought to require intelligence.
2. The branch of computer science concerned with the development of machines having this ability.
3. artificial intelligence (AI): The capability of a device to perform functions that are normally associated with human intelligence, such as reasoning and optimization through experience. Note: AI is the branch of computer science that attempts to approximate the results of human reasoning by organizing and manipulating factual and heuristic knowledge. Areas of AI activity include expert systems, natural language understanding, speech recognition, vision, and robotics.
The branch of computer science concerned with making computers behave like humans. The term was coined in 1956 by John McCarthy at the Massachusetts Institute of Technology. Artificial intelligence includes
• games playing: programming computers to play games such as chess and checkers
• expert systems : programming computers to make decisions in real-life situations (for example, some expert systems help doctors diagnose diseases based on symptoms)
• natural language : programming computers to understand natural human languages
• neural networks : Systems that simulate intelligence by attempting to reproduce the types of physical connections that occur in animal brains
• robotics : programming computers to see and hear and react to other sensory stimuli
Currently, no computers exhibit full artificial intelligence (that is, are able to simulate human behavior). The greatest advances have occurred in the field of games playing. The best computer chess programs are now capable of beating humans. In May, 1997, an IBM super-computer called Deep Blue defeated world chess champion Gary Kasparov in a chess match.
In the area of robotics, computers are now widely used in assembly plants, but they are capable only of very limited tasks. Robots have great difficulty identifying objects based on appearance or feel, and they still move and handle objects clumsily.
Natural-language processing offers the greatest potential rewards because it would allow people to interact with computers without needing any specialized knowledge. You could simply walk up to a computer and talk to it. Unfortunately, programming computers to understand natural languages has proved to be more difficult than originally thought. Some rudimentary translation systems that translate from one human language to another are in existence, but they are not nearly as good as human translators. There are also voice recognition systems that can convert spoken sounds into written words, but they do not understand what they are writing; they simply take dictation. Even these systems are quite limited -- you must speak slowly and distinctly.
In the early 1980s, expert systems were believed to represent the future of artificial intelligence and of computers in general. To date, however, they have not lived up to expectations. Many expert systems help human experts in such fields as medicine and engineering, but they are very expensive to produce and are helpful only in special situations.
Today, the hottest area of artificial intelligence is neural networks, which are proving successful in a number of disciplines such as voice recognition and natural-language processing.
There are several programming languages that are known as AI languages because they are used almost exclusively for AI applications. The two most common are LISP and Prolog.
Artificial intelligence (AI) is the intelligence of machines and the branch of computer science that aims to create it
A production system
consists of a set of rules that are in if-then form. That is given a particular situation, what are the actions to be performed. For example, if it is raining then take umbrella.
Production system also contains knowledge base, control strategy and a rule applier. To solve a problem, a system will compare the present situation with the left hand side of the rules. If there is a match then the system will perform the actions described in the right hand side of the corresponding rule.
A production system (or production rule system) is a computer program typically used to provide some form of artificial intelligence, which consists primarily of a set of rules about behavior. These rules, termed productions, are a basic representation found useful in automated planning, expert systems and action selection. A production system provides the mechanism necessary to execute productions in order to achieve some goal for the system.
Productions consist of two parts: a sensory precondition (or "IF" statement) and an action (or "THEN"). If a production's precondition matches the current state of the world, then the production is said to be triggered. If a production's action is executed, it is said to have fired. A production system also contains a database, sometimes called working memory, which maintains data about current state or knowledge, and a rule interpreter. The rule interpreter must provide a mechanism for prioritizing productions when more than one is triggered.
A production system is a tool used in artificial intelligence and especially within the applied AI domain known as expert systems. Production systems consist of a database of rules, a working memory, a matcher, and a procedure that resolves conflicts between rules. These components are outlined below. Several different versions of productions systems have been developed, including the OPs series which culminated in OPS5 (see Forgy). OPS5 was modified to implement the Soar production system described elsewhere in this document.
The rules of a production consist of a condition and action in the form: (if x then y). The left-hand-side conditions (x and y may be arbitrarily complex conjunctions of expressions) are compared against the elements of working memory to determine if the conditions are satisfied. Matching is an computationally intense procedure although the RETE algorithm of OPS5 is significantly more efficient than a simple condition-by-condition matcher.
At any point in processing, several productions may match to the elements of working memory simultaneously. Since production systems are normally implemented on serial computers, this results in a conflict: there is a non-unique choice about which action to take next. Most conflict resolution schemes are very simple, dependent on the number of conditions in the production, the time stamps (ages) of the elements to which the conditions matched, or completely random. One of the advantages of production systems is that the computational complexity of the matcher, while large, is deterministically finite and the conflict resolution scheme is trivial. This is in contrast to logicist systems in which declarative knowledge may be accessed instantly but the time required to use the knowledge (in a theorem prover, for instance) can not be pre-determined.
The actions of productions are manipulations to working memory. Elements may be added, deleted and modified. Since elements may be added and deleted, the production system is non-monotonic: the addition of new knowledge may obviate previous knowledge. Non-monotonicity increases the significance of the conflict resolution scheme since productions which match in one cycle may not match in the following because of the action of the intervening production. Some production systems are monotonic, however, and only add elements to working memory, never deleting or modifying knowledge through the action of production rules. Such systems may be regarded as implicitly parallel since all rules that match will be fired regardless of which is fired first.
Architectures using explicit productions include:
• A Meta-reasoning Architecture for 'X' (MAX)
Production System. Types of Production Systems.
A system that uses this form of knowledge representation is called a production system.
IF the initial state is a goal state THEN quit.
The major components of an AI production system are
i. A global database
ii. A set of production rules and
iii. A control system
The goal database is the central data structure used by an AI production system. The production system. The production rules operate on the global database. Each rule has a precondition that is either satisfied or not by the database. If the precondition is satisfied, the rule can be applied. Application of the rule changes the database. The control system chooses which applicable rule should be applied and ceases computation when a termination condition on the database is satisfied. If several rules are to fire at the same time, the control system resolves the conflicts.
Four 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.
Advantages of production systems:-
1. Production systems provide an excellent tool for structuring AI programs.
2. Production Systems are highly modular because the individual rules can be added, removed or modified independently.
3. The production rules are expressed in a natural form, so the statements contained in the knowledge base should the a recording of an expert thinking out loud.
Disadvantages of Production Systems:-
One important disadvantage is the fact that it may be very difficult analyse the flow of control within a production system because the individual rules don’t call each other.
Production systems describe the operations that can be performed in a search for a solution to the problem. They can be classified as follows.
Monotonic production system :- A system in which the application of a r4ule never prevents the later application of another rule, that could have also been applied at the time the first rule was selected.
Partially commutative production system:-
A production system in which 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 Y.
Theorem proving falls under monotonic partially communicative system. Blocks world and 8 puzzle problems like chemical analysis and synthesis come under monotonic, not partially commutative systems. Playing the game of bridge comes under non monotonic , not partially commutative system.
For any problem, several production systems exist. Some will be efficient than others. Though it may seem that there is no relationship between kinds of problems and kinds of production systems, in practice there is a definite relationship.
Partially commutative , monotonic production systems are useful for solving ignorable problems. These systems are important for man implementation standpoint because they can be implemented without the ability to backtrack to previous states, when it is discovered that an incorrect path was followed. Such systems increase the efficiency since it is not necessary to keep track of the changes made in the search process.
Monotonic partially commutative systems are useful for problems in which changes occur but can be reversed and in which the order of operation is not critical (ex: 8 puzzle problem).
Production systems that are not partially commutative are useful for many problems in which irreversible changes occur, such as chemical analysis. When dealing with such systems, the order in which operations are performed is very important and hence correct decisions have to be made at the first time itself.
Production System Characteristics
Production systems are important in building intelligent matches which can provide us a good set of production rules, for solving problems.
There are four types of production system characteristics, namely
1. Monotonic production system
2. Non-monotonic production system
3. Commutative law based production system, and lastly
4. Partially commutative law based production system
1. Monotonic Production System (MPS): The Monotonic production system (MPS) is a system in which the application of a rule never prevents later application of the another rule that could also have been applied at the time that the first rule was selected
2. Non-monotonic Production (NMPS): The non-monotonic production system is a system in which the application of a rule prevents the later application of the another rule which may not have been applied at the time that the first rule was selected, i.e. it is a system in which the above rule is not true, i.e. the monotonic production system rule not true.
3. Commutative Law Based Production System (CBPS): Commutative law based production systems is a system in which it satisfies both monotonic & partially commutative.
4. Partially Commutative Production System (PCPS): The partially commutative production system is a system with the property that if the application of those rules that is allowable & also transforms from state x to state ‘y’.
Laws (Characteristics) Monotonic (Characteristics) Non-monotonic
Partially commutative Theorem proving Robot navigation
Non-partial commutative Chemical synthesis Bridge game
Well the question may arise here such as:
- can the production systems be described by a set of characteristics?
- Also, can we draw the relationship between problem types & the types of production systems, suited to solve the problems, yes, we can by using above rules.
What is Transposition Table?
A transposition table is a table of previously encountered game states, together with their backed-up minimax values. Whenever a new state is generated, if it is stored in the transposition table, its stored value is used instead of searching the tree below the node. Transposition table can be used very effectively so that reachable search depth in chess, for example, can be doubled.
Complexity In Heuristic Search
December 18th, 2009 | Author: Robin
Heuristic Search: Complexity Of Finding Optimal Solutions
The time complexity of a heuristic search algorithm depends on the accuracy of the heuristic function. For example, if the heuristic evaluation function is an exact estimator, then A* runs in linear time, expanding only those nodes on an optimal solution path. Conversely, with a heuristic that returns zero everywhere, A* becomes uniform-cost search which has exponential complexity.
In general, the time complexity of A* and IDA* is an exponential function of the error in the heuristic function. For example, if the heuristic has constant absolute error, meaning that it never underestimates by more than a constant amount regardless of the magnitude of the estimate, then the running time of A* linear with respect to the solution cost. A more realistic assumption is constant relative error, which means that the error is a fixed percentage of the quantity being estimated. In that case, the running times of A* and IDA* are exponential. The base of the exponent, however, is smaller than the brute-force branching factor, reducing the asymptomatic complexity and allowing larger problems to be solved. For example, using appropriate admissible heuristic functions, IDA* can optimally solve random instance of the twenty-four puzzle and Rubik’s cube.
Depth First Search
December 18th, 2009 | Author: Robin
Depth First Search Algorithm
Depth First Search (DFS) searches deeper into the problem space. Breadth-first search always generates successor of the deepest unexpanded node. Depth First Search uses last-in first-out stack for keeping the unexpanded nodes. More commonly, depth-first search is implemented recursively, with the recursion stack taking the place of an explicit node stack.
Algorithm: Depth First Search
1.If the initial state is a goal state, quit and return success.
2.Otherwise, loop until success or failure is signaled.
a) Generate a state, say E, and let it be the successor of the initial state. If there is no successor, signal failure.
b) Call Depth-First Search with E as the initial state.
c) If success is returned, signal success. Otherwise continue in this loop.
Advantages of Depth-First Search
1. The advantage of depth-first Search is that memory requirement is only linear with respect to the search graph. This is in contrast with breadth-first search which requires more space. The reason is that the algorithm only needs to store a stack of nodes on the path from the root to the current node.
2. The time complexity of a depth-first Search to depth d is O(b^d) since it generates the same set of nodes as breadth-first search, but simply in a different order. Thus practically depth-first search is time-limited rather than space-limited.
3. If depth-first search finds solution without exploring much in a path then the time and space it takes will be very less.
Disadvantages of Depth-First Search
1. The disadvantage of Depth-First Search is that there is a possibility that it may go down the left-most path forever. Even a finite graph can generate an infinite tree. One solution to this problem is to impose a cutoff depth on the search. Although the ideal cutoff is the solution depth d and this value is rarely known in advance of actually solving the problem. If the chosen cutoff depth is less than d, the algorithm will fail to find a solution, whereas if the cutoff depth is greater than d, a large price is paid in execution time, and the first solution found may not be an optimal one.
2. Depth-First Search is not guaranteed to find the solution.
3. And there is no guarantee to find a minimal solution, if more than one solution exists.
December 18th, 2009 | Author: Robin
Uniform-Cost Search Algorithm
If all the edges in the search graph do not have the same cost then breadth-first search generalizes to uniform-cost search. Instead of expanding nodes in order of their depth from the root, uniform-cost search expands nodes in order of their cost from the root. At each step, the next step n to be expanded is one whose cost g(n) is lowest where g(n) is the sum of the edge costs from the root to node n. The nodes are stored in a priority queue. This algorithm is also known as Dijkstra’s single-source shortest algorithm.
Whenever a node is chosen for expansion by uniform cost search, a lowest-cost path to that node has been found. The worst case time complexity of uniform-cost search is O(bc/m), where c is the cost of an optimal solution and m is the minimum edge cost. Unfortunately, it also suggests the same memory limitation as breadth-first search.
Learning Real-Time A* (LRTA*) Search
If a problem is to be solved repeatedly with the same goal state but different intial state then one would like an algorithm that improves its performance over time. Learning Real-Time A* (LRTA*) is such an algorithm. It behaves almost identically to RTA*, except that instead of stroring the second-best f value of a node as its new heuristic value, it stores the best value instead. Once one problem instance is solved, the stored heuristic values are saved and become the minimal value for the next problem instance.
While LRTA* is less efficienct than RTA* for solving a sinle problem instance, if it starts with admissible initial heuristic values over repeated trials, its heuristic values eventually coverge to their exact values. At which point the algorithm returns optimal solutions.
What is Expert System?
Expert system is an artificial intelligence program that has expert-level knowledge about a particular domain and knows how to use its knowledge to respond properly. Domain refers to the area within which the task is being performed. Ideally the expert systems should substitute a human expert. Edward Feigenbaum of Stanford University has defined expert system as “an intelligent computer program that uses knowledge and inference procedures to solve problems that are difficult enough to require significant human expertise for their solutions.” It is a branch of artificial intelligence introduced by researchers in the Stanford Heuristic Programming Project.
The expert systems is a branch of AI designed to work within a particular domain. As an expert is a person who can solve a problem with the domain knowledge in hands it should be able to solve problems at the level of a human expert. The source of knowledge may come come from a human expert and/or from books, magazines and internet. As knowledge play a key role in the functioning of expert systems they are also known as knowledge-based systems and knowledge-based expert systems. The expert’s knowledge about solving the given specific problems is called knowledge domain of the expert.
Components of Expert Systems
Figure: Expert System
Basic Concept of an Expert System Function
The expert system consists of two major components: knowledge base and inference engine.
Knowledge base contains the domain knowledge which is used by the inference engine to draw conclusions. The inference engine is the generic control mechanism that applies the axiomatic knowledge to the task-specific data to arrive at some conclusion. When a user supplies facts or relevant information of query to the expert system he receives advice or expertise in response. That is given the facts it uses the inference engine which in turn uses the knowledge base to infer the solution.
Characteristics of Expert Systems
High performance: They should perform at the level of a human expert.
Adequate response time: They should have the ability to respond in a reasonable amount of time. Time is crucial especially for real time systems.
Reliability: They must be reliable and should not crash.
Understandable: They should not be a black box instead it should be able explain the steps of the reasoning process. It should justify its conclusions in the same way a human expert explains why he arrived at particular conclusion.
A shell is a special purpose tool designed based on the requirements of particular applications. User should supply the knowledge base to the shell. Example for the shell is EMYCIN (Empty MYCIN) shell. Shell manages the input and output. It processes the information given by the user, relates it to the concepts contained in the knowledge base, and provides solution for a particular problem.
Advantages of Expert Systems
Availability: Expert systems are availabe easily due to mass production software.
Cheaper: The cost of providing expertise is not expensive.
Reduced danger: They can be used in any risky environments where humans cannot work with.
Permanence: The knowledge will last long indefinitely.
Multiple expertise: It can be designed to have knowledge of many experts.
Explanation: They are capable of explaining in detail the reasoning that led to a conclusion.
Fast response: They can respond at great speed due to the inherent adavantages of computers over humans.
Unemotional and repsonse at all times: Unlike humans, they do not get tense, fatigue or panic and work steadily during emergency situations.