9450 SW Gemini Drive #32865
Beaverton, Oregon, 97008-7105
AI Planning Systems is a branch of Artificial Intelligence whose purpose is to identify strategies and action sequences that will, with a reasonable degree of confidence, enable the AI program to deliver the correct answer, solution, or outcome.
As I explained in a previous article Solve General Problems with Artificial Intelligence, one of the limitations of early AI, which was based on the physical symbol system hypothesis (PSSH), is combinatorial explosion — a mathematical phenomenon in which the number of possible combinations increases beyond the computer's capability to explore all of them in a reasonable amount of time.
AI planning attempts to solve the problem of combinatorial explosion by using something called heuristic reasoning — an approach that attempts to give artificial intelligence a form of common sense. Heuristic reasoning enables an AI program to rule out a large number of possible combinations by identifying them as impossible or highly unlikely. This approach is sometimes referred to as "limiting the search space."
A heuristic is a mental shortcut or rule-of-thumb that enables people to solve problems and make decisions quickly. For example, the Rule of 72 is a heuristic for estimating the number of years it would take an investment to double your money. You divide 72 by the rate of return, so an investment with a 6% rate of return would double your money in about 72/6 = 12 years.
Heuristic reasoning is common in innovation. Inventors rarely consider all the possibilities for solving a particular problem. Instead, they start with an idea, a hypothesis, or a hunch based on their knowledge and prior experience, then they start experimenting and exploring from that point forward. If they were to consider all the possibilities, they would waste considerable time, effort, energy, and expertise on futile experiments and research.
With AI planning, you might combine heuristic reasoning with a physical symbol system to improve performance. For example, imagine heuristic reasoning applied to the Chinese room experiment I introduced in my previous post on the general problem solver.
In the Chinese room scenario, you, an English-only speaker, are locked in a room with a narrow slot on the door through which notes can pass. You have a book filled with long lists of statements in Chinese, and the floor is covered in Chinese characters. You are instructed that upon receiving a certain sequence of Chinese characters, you are to look up a corresponding response in the book and, using the characters strewn about the floor, formulate your response.
What you do in the Chinese room is very similar to how AI programs work. They simply identify patterns, look up entries in a database that correspond to those patterns, and output the entries in response.
With the addition of heuristic reasoning, AI could limit the possibilities of the first note. For example, you could program the software to expect a message such as "Hello" or "How are you?” In effect, this would limit the search space, so that the AI program had to search only a limited number of records in its database to find an appropriate response. It wouldn't get bogged down searching the entire database to consider all possible messages and responses.
The only drawback is that if the first message was not one of those that was anticipated, the AI program would need to search its entire database.
Heuristic reasoning is commonly employed in modern AI applications. For example, if you enter your location and destination in a GPS app, the app doesn't search its vast database of source data, which consists of satellite and aerial imagery; state, city, and county maps; the US Geological Survey; traffic data; and so on. Instead, it limits the search space to the area that encompasses the location and destination you entered. In addition, it limits the output to the fastest or shortest route (not both) depending on which setting is in force, and it likely omits a great deal of detail from its maps to further expedite the process.
The goal is to deliver an accurate map and directions, in a reasonable amount of time, that lead you from your current location to your desired destination as quickly as possible. Without the shortcuts to the process provided by heuristic reasoning, the resulting combinatorial explosion would leave you waiting for directions... possibly for the rest of your life.
Even though many of the modern AI applications are built on what are now considered old-fashioned methods, AI planning allows for the intelligent combination of these methods, along with newer methods, to build AI applications that deliver the desired output. The resulting applications can certainly make computers appear to be intelligent beings — providing real-time guidance from point A to point B, analyzing contracts, automating logistics, and even building better video games.
If you're considering a new AI project, don't be quick to dismiss the benefits of good old-fashioned AI (GOFAI). Newer approaches may not be the right fit.
In a previous post entitled "Playing the Imitation Game," I discussed Alan Turing's vision, published in 1936, of a single, universal machine that could be programmed to solve any particular problem. In 1959, Allen Newell and Herbert A. Simon took a different approach. Their goal was to develop a computer program that could function as a universal problem solver.
Newell and Simon - Courtesy Carnegie Mellon University Libraries
In theory, their general problem solver (GPS) would be able to solve any problem that could be presented in the form of specific types of mathematical formulas that are useful in programming logic. This type of problem would include geometric proofs, which start with definitions, axioms (statements accepted as fact), postulates, and previously proven theorems, and use logic to arrive at reasoned conclusions.
One of the problems GPS solved was the Tower of Hanoi — a game or puzzle consisting of three rods and a number of disks of different sizes, which can slide onto any rod.
When you start, all the disks are on one rod, ordered from largest to smallest from the bottom up. The goal is to move the entire stack to another rod in the least number of moves following these rules:
● Move only one disk at a time.
● Do not place a larger disk on top of a smaller one.
● Each move consists of taking the top disk from one stack and placing it on an empty rod or on the top of an existing stack.
The minimum number of moves to solve the Tower of Hanoi is 2n – 1, where n is the number of disks, so for three disks, the minimum number of moves is (2 x 2 x 2) – 1 = 7.
One of the key parts of the general problem solver was what Newell and Simon called the physical symbol system hypothesis (PSSH). According to Newell and Simon, "A physical symbol system has the necessary and sufficient means for general intelligent action." Such a system would be able to take patterns (symbols), combine them into structures (expressions), and manipulate them using various processes to produce new expressions.
Newell and Simon believed that human intelligence was no more than a complex physical symbol system. They thought that a key part of human reasoning consisted merely of connecting symbols — that our language, ideas, and concepts were just broad groupings of interconnected symbols. For example, when we see a chair or a picture of a chair, we associate it with the act of sitting. When we smell smoke, we associate it with fire, which is associated with danger, which may trigger a fight-or-flight response.
Newell and Simon argued that by feeding a machine enough physical symbols, creating a sufficient number of associations, and putting rules in place for combining symbols into structures and manipulating them to create new expressions, machines could be made to "think" like we humans do. This theory forms the basis of what drives most of machine learning and artificial intelligence to this day.
Not everyone buys into the notion that a physical symbol system is necessary and sufficient for human intelligence. In 1980, philosopher John Searle argued that merely connecting symbols could not be considered intelligence. To support his argument against the idea that manipulating physical symbols constituted intelligence, he presented what is commonly referred to as the Chinese room argument.
Imagine yourself, an English-only speaker, locked in a room with a narrow slot on the door through which you can pass notes. You have a book filled with long lists of statements in Chinese, and the floor is covered in Chinese characters. You are instructed that upon receiving a certain sequence of Chinese characters, you are to look up a corresponding response in the book and, using the characters strewn about the floor, formulate your response.
Someone outside the room who speaks and writes fluent Chinese writes a note on a sheet of paper and passes it to you through the slot on the door. Following the instructions you were given, you look up a response in the book, copy the response using characters from the floor to create your note, and pass it through the slot to the person who delivered the original message.
The native speaker may believe that the two of you are communicating and that you know the language. However, Searle argues that this is no proof of intelligence, because you have no understanding of the messages you are receiving or sending.
You can try a similar experiment with your smart phone. If you ask Siri or Alexa how she's feeling, she will answer your question even though she feels nothing at all. She doesn't even understand the question. This artificially "intelligent" being is merely matching your question to what is considered an acceptable answer and delivering that answer to you.
A huge obstacle to achieving artificial intelligence through a physical symbol system is what's known as combinatorial explosion — the rapid growth of symbol combinations that makes pattern-matching increasingly difficult. Combinatorial explosion is far greater than exponential growth. The formula for exponential growth can be expressed as y = 2x, whereas the formula for combinatorial explosion is y = x! (the factorial of x). For example, if x = 20, then
exponential growth: y = 2x = 220 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 1,048,576
combinatorial explosion: y = x! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 x 17 x 18 x 19 x 20 = 2,432,902,008,176,640,000
With each added symbol, the number of combinations increases dramatically. Considering all the possible combinations would require immense computational resources over a considerable amount of time.
Even with these challenges, pattern-matching has remained the cornerstone of artificial intelligence, regardless of whether it is even in the same ballpark as human intelligence.