Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
2000-12-04
2002-09-03
Starks, Jr., Wilbert L. (Department: 2122)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S048000, C706S058000
Reexamination Certificate
active
06446057
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to backtracking-based searching, and in particular to transparent backtracking-based searching.
2. Background Art
Backtracking-based searching is a mechanism for solving complex problems having many potential alternative solutions. Rather than analyzing all possible alternatives prior to choosing a solution, a system using backtracking investigates one alternative at a time until an acceptable alternative is found.
In the prior art, special purpose logic-programming computer languages have been created that can be used to write a backtracking search program. Special purpose languages cannot take advantage of the tool sets that are typically available for general purpose programming languages. Further it is necessary for a developer to become proficient in the special purpose language (e.g., learn its syntax and programming strategies) before writing or developing a software application using the special purpose language.
One example of a special purpose programming language used for backtrack search applications is Prolog. Prolog operates on rules or clauses. Prolog attempts to match a first clause expressed in the rules with another clause that partially matches the first clause, or a literal statement of data. If multiple matches are found, Prolog chooses one of them. If the chosen alternative fails, Prolog backtracks to the point at which the failed match was chosen, and chooses another alternative.
Prolog has a built-in control flow capability that identifies matches, and arranges for backtracking when alternatives fail. Prolog organizes problems into a tree of “choice points”, called a “decision tree”. A choice point represents a point at which a decision must be made between a set of alternative selections. Each alternative represents a branch of the decision tree. At each choice point, Prolog chooses a branch, and explores that branch to determine whether it leads to an acceptable solution. If the chosen branch does not produce a solution, Prolog backtracks to the choice point and tries a different branch. As part of the backtracking process, before proceeding down a new branch, Prolog must restore the state of execution that existed at the choice point before the previously tried branch. That is, the data state (i.e. values of variables) and the control state (i.e. execution stack) must be restored to what they were before the previous branch was tried.
Another example of a special purpose language that is used to perform backtracking is described in T. A. Budd, “Blending Imperative and Relational Programming,”
IEEE Software
, January 1991, pp. 58-65. The special purpose language, Leda, includes logic programming such as that provided by Prolog and procedural programming derived from Algol-like languages. Leda is a proprietary language that has its own syntax and programming restrictions. One such restriction requires that data types possess some value that indicates an “undefined” state which indicates that a value has not yet been assigned. All variables are undefined before the first use and cannot be used until defined without raising a runtime error.
The relational portion of Leda is fashioned after Prolog. Leda uses rules as in Prolog. The rules can contain calls to imperative functions. However, the imperative functions must return a Boolean value. Choice points are generated at run time based on the rules or a Suspend statement in Leda. A special compiler is needed to compile the Leda proprietary language.
Since Leda is a proprietary language, it does not provide a solution to the problem of implementing a backtracking mechanism using a general purpose language such as C++, for example. It is not possible to use the wide array of tool sets that are available for the general purpose languages.
L. Nigro, “Control Extensions in C++”,
Journal of Object-Oriented Programming
, Febuary 1994, pp. 37-47 describes control extensions to C++ based on threads. Threads are control objects capable of independent execution. A thread is provided with features allowing temporary suspension and later resumption of its execution. A backtracking class is identified as a control extension of the thread class.
The backtracking class makes a copy of the computational state at a point in execution where a decision is made from among a list of alternatives (e.g., a choice point). In the process of choosing an alternative, a choice point is created and the computational state (i.e., data and execution state) is copied to a duplicate thread.
A failure method of the backtracking class is called to roll the execution state of the current thread back to the most recent choice point and return the next integer (representing the next alternative) in the sequence. To roll back the execution state, the duplicate thread is copied to the current thread.
Thus, in Nigro, the backtracking is performed by storing a copy of the entire execution stack and data state in the duplicate thread so that they can be restored during backtracking. This results in significant overhead due to the processing needed to copy the duplicate thread into the current thread, and due to the memory resources needed to store the duplicate thread. If backtracking is relatively infrequent, this overhead is wasted. Further, to dispose of the execution state of the failed alternative, Nigro's approach results in additional overhead since it is necessary to copy the duplicate thread back to the current thread. Nigro must perform a copy operation to transfer the archived execution state (i.e., the duplicate thread) to the current thread to dispose of the failed alternative's execution state.
Nigro's approach does not address resource allocation and deallocation. The duplicate thread assumes a certain state of resource allocation. When the duplicate thread is transferred to the current thread, unpredictable situations may occur due to a changed state of resource allocation. For example, memory is allocated to store a local string variable after which the duplicate thread is created. The current thread continues and the memory allocated to store a local string variable is released when the method in which the string variable is used terminates. When the current thread is recreated using the duplicate thread, the resource is no longer allocated. However, the restored thread assumes that the memory is still allocated for the local string variable. Use of the local string variable by the restored thread results in reading from unallocated memory which is likely to lead to an invalid execution state or an abnormal termination.
To implement backtracking in a general purpose language, current techniques encode logic for backtracking explicitly in the program which restricts the control flow of the search program. The backtracking logic can be encoded in a program using a recursive search engine that recursively calls itself to perform the search. Each call to itself represents a node, or choice point, on the search's decision tree.
The following is a pseudocode example of a recursive search routine. The search routine operates with a data state that includes an ordered list of steps or goals each of which must be satisfied for the search to be successful.
boolean search( )
{
If there are no goals remaining, return true;
ask the first goal for a set of alternatives
for each such alternative
{
make the side-effects associated with the alternative
if search( ), return true
unmake the side-effects associated with the alternative
}
return false
}
There are many variations of a recursive technique for writing search programs with general purpose languages. However, each recursive search routine imposes a fundamental restriction on the structure of the search program. The problem domain of the search must necessarily be divided into goals each of which has a set of alternatives and a set of side-effects. As discussed below, one example of a side-effect is a subgoal of a complex goal.
One or more of
LandOfFree
Method and apparatus for transparent backtracking does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for transparent backtracking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for transparent backtracking will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2882711