Artificial Intelligence (AI) is the area of computer science focusing on creating machines that can engage on behaviors that humans consider intelligent. The ability to create intelligent machines has intrigued humans since ancient times, and today with the advent of the computer and 50 years of research into AI programming techniques, the dream of smart machines is becoming a reality. Researchers are creating systems which can mimic human thought, understand speech, beat the best human chess player, and countless other feats never before possible. Find out how the military is applying AI logic to its hi-tech systems, and how in the near future Artificial Intelligence may impact our lives.
To understand what exactly artificial intelligence is, we illustrate some common problems. Problems dealt with in artificial intelligence generally use a common term called 'state'. A state represents a status of the solution at a given step of the problem solving procedure. The solution of a problem, thus, is a collection of the problem states. The problem solving procedure applies an operator to a state to get the next state. Then it applies another operator to the resulting state to derive a new state. The process of applying an operator to a state and its subsequent transition to the next state, thus, is continued until the goal (desired) state is derived. Such a method of solving a problem is generally referred to as state space approach. We will first discuss the state-space approach for problem solving by a well-known problem, which most of us perhaps have solved in our childhood.
Researchers in artificial intelligence have segregated the AI problems from the non-AI problems. Generally, problems, forwhich straightforward mathematical / logical algorithms are not readily available and which can be solved by intuitive approach only, are called AI problems. The 4-puzzle problem, for instance, is an ideal AI Problem. There is no formal algorithm for its realization, i.e., given a starting and a goal state, one cannot say prior to execution of the tasks the sequence of steps required to get the goal from the starting state. Such problems are called the ideal AI problems. The well known water-jug problem, the Travelling Salesperson Problem (TSP) , and the n-Queen problem are typical examples of the classical AI problems. Among the non-classical AI problems, the diagnosis problems and the pattern classification problem need special mention. For solving an AI problem, one may employ both artificial intelligence and non-AI algorithms. An obvious question is: what is an AI algorithm? Formally speaking, an artificial intelligence algorithm generally means a non-conventional intuitive approach for problem solving. The key to artificial intelligence approach is intelligent search and matching. In an intelligent search problem / sub-problem, given a goal (or starting) state, one has to reach that state from one or more known starting (or goal) states.
The question that then naturally arises is: how to control the generation of states. This, in fact, can be achieved by suitably designing some control strategies, which would filter a few states only from a large number of legal states that could be generated from a given starting / intermediate state. As an example, consider the problem of proving a trigonometric identity that children are used to doing during their schooldays. What would they do at the beginning? They would start with one side of the identity, and attempt to apply a number of formulae there to find the possible resulting derivations. But they won't really apply all the formulae there. Rather, they identify the right candidate formula that fits there best, such that the other side of the identity seems to be closer in some sense (outlook). Ultimately, when the decision regarding the selection of the formula is over, they apply it to one side (say the L.H.S) of the identity and derive the new state. Thus they continue the process and go on generating new intermediate states until the R.H.S (goal) is reached. But do they always select the right candidate formula at a given state? From our experience, we know the answer is "not always". But what would we do if we find that after generation of a few states, the resulting expression seems to be far away from the R.H.S of the identity. Perhaps we would prefer to move to some old state, which is more promising, i.e., closer to the R.H.S of the identity. The above line of thinking has been realized in many intelligent search problems of AI. Some of these well-known search algorithms are:
* Generate and Test
* Hill Climbing
* Heuristic Search
* Means and Ends analysis
Generate and Test Approach: This approach concerns the generation of the state-space from a known starting state (root) of
the problem and continues expanding the reasoning space until the goal node or the terminal state is reached. In fact after
generation of each and every state, the generated node is compared with the known goal state. When the goal is found, the
algorithm terminates. In case there exist multiple paths leading to the goal, then the path having the smallest distance from
the root is preferred. The basic strategy used in this search is only generation of states and their testing for goals but it
does not allow filtering of states.
(b) Hill Climbing Approach: Under this approach, one has to first generate a starting state and measure the total cost for
reaching the goal from the given starting state. Let this cost be f. While f = a predefined utility value and the goal is not
reached, new nodes are generated as children of the current node. However, in case all the neighborhood nodes (states) yield
an identical value of f and the goal is not included in the set of these nodes, the search algorithm is trapped at a hillock
or local extrema. One way to overcome this problem is to select randomly a new starting state and then continue the above
search process. While proving trigonometric identities, we often use Hill Climbing, perhaps unknowingly.
(c) Heuristic Search: Classically heuristics means rule of thumb. In heuristic search, we generally use one or more heuristic
functions to determine the better candidate states among a set of legal states that could be generated from a known state.
The heuristic function, in other words, measures the fitness of the candidate states. The better the selection of the states,
the fewer will be the number of intermediate states for reaching the goal. However, the most difficult task in heuristic
search problems is the selection of the heuristic functions. One has to select them intuitively, so that in most cases
hopefully it would be able to prune the search space correctly. We will discuss many of these issues in a separate chapter on
Intelligent Search.
(d) Means and Ends Analysis: This method of search attempts to reduce the gap between the current state and the goal state.
One simple way to explore this method is to measure the distance between the current state and the goal, and then apply an
operator to the current state, so that the distance between the resulting state and the goal is reduced. In many mathematical
theorem- proving processes, we use Means and Ends Analysis.
To understand what exactly artificial intelligence is, we illustrate some common problems. Problems dealt with in artificial intelligence generally use a common term called 'state'. A state represents a status of the solution at a given step of the problem solving procedure. The solution of a problem, thus, is a collection of the problem states. The problem solving procedure applies an operator to a state to get the next state. Then it applies another operator to the resulting state to derive a new state. The process of applying an operator to a state and its subsequent transition to the next state, thus, is continued until the goal (desired) state is derived. Such a method of solving a problem is generally referred to as state space approach. We will first discuss the state-space approach for problem solving by a well-known problem, which most of us perhaps have solved in our childhood.
Researchers in artificial intelligence have segregated the AI problems from the non-AI problems. Generally, problems, forwhich straightforward mathematical / logical algorithms are not readily available and which can be solved by intuitive approach only, are called AI problems. The 4-puzzle problem, for instance, is an ideal AI Problem. There is no formal algorithm for its realization, i.e., given a starting and a goal state, one cannot say prior to execution of the tasks the sequence of steps required to get the goal from the starting state. Such problems are called the ideal AI problems. The well known water-jug problem, the Travelling Salesperson Problem (TSP) , and the n-Queen problem are typical examples of the classical AI problems. Among the non-classical AI problems, the diagnosis problems and the pattern classification problem need special mention. For solving an AI problem, one may employ both artificial intelligence and non-AI algorithms. An obvious question is: what is an AI algorithm? Formally speaking, an artificial intelligence algorithm generally means a non-conventional intuitive approach for problem solving. The key to artificial intelligence approach is intelligent search and matching. In an intelligent search problem / sub-problem, given a goal (or starting) state, one has to reach that state from one or more known starting (or goal) states.
The question that then naturally arises is: how to control the generation of states. This, in fact, can be achieved by suitably designing some control strategies, which would filter a few states only from a large number of legal states that could be generated from a given starting / intermediate state. As an example, consider the problem of proving a trigonometric identity that children are used to doing during their schooldays. What would they do at the beginning? They would start with one side of the identity, and attempt to apply a number of formulae there to find the possible resulting derivations. But they won't really apply all the formulae there. Rather, they identify the right candidate formula that fits there best, such that the other side of the identity seems to be closer in some sense (outlook). Ultimately, when the decision regarding the selection of the formula is over, they apply it to one side (say the L.H.S) of the identity and derive the new state. Thus they continue the process and go on generating new intermediate states until the R.H.S (goal) is reached. But do they always select the right candidate formula at a given state? From our experience, we know the answer is "not always". But what would we do if we find that after generation of a few states, the resulting expression seems to be far away from the R.H.S of the identity. Perhaps we would prefer to move to some old state, which is more promising, i.e., closer to the R.H.S of the identity. The above line of thinking has been realized in many intelligent search problems of AI. Some of these well-known search algorithms are:
* Generate and Test
* Hill Climbing
* Heuristic Search
* Means and Ends analysis
Generate and Test Approach: This approach concerns the generation of the state-space from a known starting state (root) of
the problem and continues expanding the reasoning space until the goal node or the terminal state is reached. In fact after
generation of each and every state, the generated node is compared with the known goal state. When the goal is found, the
algorithm terminates. In case there exist multiple paths leading to the goal, then the path having the smallest distance from
the root is preferred. The basic strategy used in this search is only generation of states and their testing for goals but it
does not allow filtering of states.
(b) Hill Climbing Approach: Under this approach, one has to first generate a starting state and measure the total cost for
reaching the goal from the given starting state. Let this cost be f. While f = a predefined utility value and the goal is not
reached, new nodes are generated as children of the current node. However, in case all the neighborhood nodes (states) yield
an identical value of f and the goal is not included in the set of these nodes, the search algorithm is trapped at a hillock
or local extrema. One way to overcome this problem is to select randomly a new starting state and then continue the above
search process. While proving trigonometric identities, we often use Hill Climbing, perhaps unknowingly.
(c) Heuristic Search: Classically heuristics means rule of thumb. In heuristic search, we generally use one or more heuristic
functions to determine the better candidate states among a set of legal states that could be generated from a known state.
The heuristic function, in other words, measures the fitness of the candidate states. The better the selection of the states,
the fewer will be the number of intermediate states for reaching the goal. However, the most difficult task in heuristic
search problems is the selection of the heuristic functions. One has to select them intuitively, so that in most cases
hopefully it would be able to prune the search space correctly. We will discuss many of these issues in a separate chapter on
Intelligent Search.
(d) Means and Ends Analysis: This method of search attempts to reduce the gap between the current state and the goal state.
One simple way to explore this method is to measure the distance between the current state and the goal, and then apply an
operator to the current state, so that the distance between the resulting state and the goal is reduced. In many mathematical
theorem- proving processes, we use Means and Ends Analysis.
No comments:
Post a Comment