Data processing: artificial intelligence – Having particular user interface
Reexamination Certificate
1999-11-04
2004-11-30
Voeltz, Emanuel Todd (Department: 2121)
Data processing: artificial intelligence
Having particular user interface
C706S045000, C706S012000
Reexamination Certificate
active
06826549
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods of operating digital computers to perform heuristic searches, and more particularly, to a system and method for solving combinatorial optimization problems.
BACKGROUND OF THE INVENTION
Practical enumerative search or combinatorial optimization problems occur in a variety of fields including scheduling, routing, design layout, engineering disciplines, management and econometrics. Solutions to these problems are characterized by identifying an optimum combination of individual choice selections from among a multitude of possibilities. Examples of such enumerative search, graph search, or combinatorial optimization problems include moves in board games such as chess or go, determining how articles of different sizes can be packed in containers of limited capacity, determining optimum scheduling of operations in a manufacturing process, and capacitated vehicle routing with time windows.
Enumerative search, or combinatorial optimization problems is a well established field, for example, see Aho et al. in “Data Structures & Algorithms,” Addison-Wesley Reading, 1983. In principle, combinatorial optimization problems can be solved by testing all possible combinations of choices and selecting only those combinations that give the most favorable result. However, other than in simple problems, the number of possible combinations rapidly becomes so large that, even when digital computers are employed, the solution of a single problem on a single processor may take hours, days, sometimes even months or years.
In the prior art, the time required to solve combinatorial optimization problems has been reduced by using efficient heuristic methods that are not guaranteed to find an optimal solution, but one that is near optimal. Typical heuristic methods combine some form of gradient-descent search to find local optima with some strategy for escaping non-optimal local optima. For to example, annealing resolves the problem of getting stuck in local optima by allowing “moves” to inferior solutions. By letting the minimizing heuristic accept occasional uphill moves, the heuristic can escape from a local optimum “gully” and eventually fall into a possible “valley” to find a global optimum. The probability to go back, that is, moving uphill, decreases with time, and the heuristic will finally “freeze” in a local optimum. However, these systems do not have any performance guarantees, and may often return solutions that are far from optimal.
One idea for improving the performance of search techniques for combinatorial optimization problems is to involve the human user in the search process via a cooperative interface technique. A specific technique that does this is called interactive evolution. Because cooperative interface paradigms like interactive evolution have been used mostly for designing various kinds of computer graphics, these are best characterized in terms of a design process rather than an optimization process. Generally, interactive-evolution systems generate successive sets of designs, based on previous designs, and a user selects which designs to accept for further refinement, and which to reject. Thus, designs evolve, subject to user-supplied selection criteria, see Kochhar et al. in “User control in cooperative computer-aided design,” Proceedings of the 1990 ACM SIGGRAPH Symposium on User Interface Software and Technology, pp. 143-151, 1990.
Constraint-based interfaces constitute yet another human-computer cooperative technique for design/optimization tasks. These are popular in drawing applications, see Nelson et al. in “The Juno-2 Constraint-Based Drawing Editor,” Digital Equipment Corp. SRC—Research Report 131
a
, 1994. Typically, the user imposes geometric or topological constraints on a nascent drawing such that subsequent manipulation is constrained to useful areas of the design space.
SUMMARY OF THE INVENTION
The invention provides a cooperative-interface technique that partitions combinatorial optimization problems into two tasks, one for the user and one for the computer processor, to facilitate a human-guided search. The processor is only responsible for finding local optima using, for example, a hill-climbing search which can be either greedy (best first) or steepest ascent (shortest). The result of the search is visualized, and the user identifies promising regions of the search space for the processor to explore. The user can also intervene to help the processor escape non-optimal local optima, or change the constraints of the optimizing function. The general strategy combines heuristic-search and information-visualization techniques in an interactive system. In a specific application, the invention is applied to the problem of capacitated vehicle routing with time windows (CVRTW).
More specifically, the invention provides a system and method that enables an interactively guided heuristic search for solving a combinatorial optimization problem. The system initially performs a greedy hill-climbing search to obtain an initial solution to a combinatorial optimization problem using initial default parameters for the search process.
The initial solution and the combinatorial optimization problem are visualized on an optimization table, a table-top display device that is suitable for group viewing and interaction. The parameters of the search process are then altered by the user based on a visualization of the combinatorial optimization problem and the initial solution. Then, the searching, visualizing, and parameter setting are repeated until the current solution is selected as an acceptable solution of the combinatorial optimization problem is by the user. The term “acceptable” is used here instead of “optimal” because the user can certainly accept a less than “optimal” solution based on facts and conditions known only to the user. Potentially, these facts and conditions could be impossible to duplicate in a pure process driven search to determine an optimal solution.
During the repeating, the search-process parameters can be a set of probabilities, if the search is a random perturbation-based search. Alternatively, the search-process parameters can be a set of priorities, if the search is an exhaustive local search.
REFERENCES:
patent: 5542043 (1996-07-01), Cohen et al.
patent: 2002/0008657 (2002-01-01), Poore, Jr.
Ki Soo Hwang et al; Constrained Conditional Resource Sharing in Pipeline Synthesis; 11/88; IEEE; CH2657-5/88/0000/0052;52-55.*
Dejan Jovanovic'c et al; Scan: A Decision Support System for Railroad Scheduling; 4/89; IEEE: CH2749-0/89/0000-0097;97-105.*
Allan Heydon et al; The Juno-2 Constraint-Based Drawing Editor; Dec. 1994; SRC; 1-19.*
Greg Nelson; Juno, a constraint-based graphics system; Jul. 22, 1985; ACM; 0-89791-166-0/85/007/0235; 235-243.*
Heydon et al., “The Juno-2 Constraint-Based Drawing Editor”; Digital Equipment Corporation; SRC-Research Report 131a, Dec., 1994.
Lesh Neal B.
Marks Joseph W.
Ratajczak David
Brinkman Dirk
Curtin Andrew
Hirl Joseph P.
Mitsubishi Electric Research Laboratories Inc.
Todd Voeltz Emanuel
LandOfFree
Interactive heuristic search and visualization for solving... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interactive heuristic search and visualization for solving..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interactive heuristic search and visualization for solving... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3294817