Method and system for algorithm synthesis in problem solving
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06E-001/00
G06F-015/18
출원번호
US-0874552
(2001-06-04)
발명자
/ 주소
Jackson, Warren B.
Fromherz, Markus P. J.
출원인 / 주소
Xerox Corporation
인용정보
피인용 횟수 :
79인용 특허 :
16
초록▼
A method for problem solving in a computer system includes an applications module for sending a problem statement to a complexity module, which configures a solving module with configuration parameters and also determines expected problem solver behavior. The solving module selects a set of paramete
A method for problem solving in a computer system includes an applications module for sending a problem statement to a complexity module, which configures a solving module with configuration parameters and also determines expected problem solver behavior. The solving module selects a set of parameter configuration vectors, determines a set of search space points, performs a partial search based on the parameter configuration vectors, and determines actual problem solver behavior. The solving module then determines whether a problem solution has been found, whether to perform a solver iteration step or request a complexity module to perform an adaptation step.
대표청구항▼
1. A problem solving method for use in a computer system, wherein the computer system includes an applications module having a problem solver, wherein the problem solver comprises a solving module and a complexity module, the method comprising:receiving a problem statement from the applications modu
1. A problem solving method for use in a computer system, wherein the computer system includes an applications module having a problem solver, wherein the problem solver comprises a solving module and a complexity module, the method comprising:receiving a problem statement from the applications module; predicting an expected problem solver behavior associated with configuration parameters for said problem statement; providing the solving module with said configuration parameters; selecting a set of configuration parameter vectors; determining a set of search space points; perform a partial search with said configuration parameter vectors; determining actual solver behavior; reviewing said actual solver behavior incrementally to determine if a problem solution has been found, wherein reviewing comprises comparing said expected solver behavior with said actual solver behavior; determining whether to perform a solver iteration step or to request the complexity module to perform an adaptation step if a problem solution has not been found, wherein said complexity module includes means for detecting problem complexity, means for estimating rate of improvement bounds, and means for selecting a complexity related action, wherein said complexity related action comprises selecting at least one member from the group consisting of returning an error, accepting the best result possible for fixed computational resources, adding computational resources, and changing the problem statement; performing a said solver iteration step when said solver iteration step is selected, comprising the steps of determining new actual solver behavior and determining whether to repeat said solver iteration step; repeating said solver iteration step until said adaptation step is selected; comparing said actual solver behavior with said expected solver behavior when said adaptation step is selected; requesting the complexity module to perform said adaptation step; performing said adaptation step, comprising the steps of modifying said configuration parameters within the complexity module, configuring the solving module with said modified configuration parameters, determining expected solver behavior associated with said modified configuration parameters for said problem statement, selecting an algorithm to calculate a revised problem solution, determining a revised actual solver behavior associated with said modified configuration parameters for said problem statement, reviewing said revised actual solver behavior to determine if a problem solution has been found, determining whether to perform said solver iteration step or to request the complexity module to perform another adaptation step if a problem solution has not been found, and repeating said iteration step until said adaptation step is selected; repeating said adaptation step until a problem solution is found; and providing the solution to the applications module. 2. The problem solving method according to claim 1, further comprising the step of selecting an algorithm to calculate an initial problem solution.3. The problem solving method according to claim 1, further comprising the step of refining the configuration parameters provided to the solving model.4. The problem solving method according to claim 1, wherein the problem solver comprises an adaptive constraint problem solver.5. The problem solving method according to claim 1, further comprising the step of transforming said problem statement after receiving said problem statement from the applications module.6. The problem solving method according to claim 1, wherein said configuration parameters include problem configuration parameters and solver configuration parameters.7. The problem solving method according to claim 6, further comprising the step of transforming said problem configuration parameters before providing said problem configuration parameters to the solving module.8. The problem solving method according to claim 1, wherein the step of selecting a set of configuration parameter vectors further comprises:choosing a set of default configuration parameter vectors; selecting an initial minimum point; performing a local search; evaluating actual behavior to determine whether to repeat a local search or select a different solver algorithm; repeating a local search with a second minimum point when the step of repeating a local search is selected; and revising the set of configuration parameter vectors for each search performed. 9. A computer system for problem solving, the system having implementation units communicating with the computer system, the system comprising:an input device for providing the problem statement; a computer coupled to the output of said input device; a memory portion coupled to the computer comprising: software for receiving the problem statement from said input device; software for determining solver configuration parameter vectors; software for configuring a problem solver, wherein said problem solver includes a solving module and a complexity module, wherein said complexity module includes means for detecting problem complexity, means for estimating rate of improvement bounds, and means for selecting a complexity related action, wherein said complexity related action comprises selecting at least one member from the group consisting of returning an error, accepting the best result possible for fixed computational resources, adding computational resources, and changing the problem statement; software for predicting expected solver behavior; software for performing a partial search with said configuration parameter vectors; software for determining actual solver behavior and incrementally determining whether a solution has been found, wherein determining whether a solution has been found comprises comparing said expected solver behavior and said actual solver behavior; software for determining whether to perform a solver iteration step or to perform an adaptation step; and software for performing an adaptation step, comprising modifying said configuration parameters and reconfiguring said problem solver; and output means for providing a solution statement. 10. The computer system for problem solving according to claim 9, wherein said problem solver comprises an adaptive constraint problem solver.11. The computer system for problem solving according to claim 9, wherein said memory portion further comprises software including a learning module for refining said expected problem solver behavior.12. The computer system for problem solving according to claim 9, further comprising a problem transformer module for transforming said problem statement after receiving said problem statement from said input device.13. The computer system for problem solving according to claim 9, wherein said configuration parameters include problem configuration parameters and solver configuration parameters.14. The computer system for problem solving according to claim 13, further comprising a problem transformer module for transforming said problem configuration parameters before providing said problem configuration parameters to said solving module.15. The computer system for problem solving according to claim 9, wherein said software for determining expected solver behavior comprises a data structure, said data structure containing configuration parameters and expected behaviors for a plurality of problem types.16. The computer system for problem solving according to claim 9, wherein the computer includes an embedded computer.17. The computer system for problem solving according to claim 16, wherein said embedded computer system controls at least one operation within a copier or printer.18. The computer system for problem solving according to claim 16, wherein said embedded computer system controls at least one operation within a process control system.19. The computer system for problem solving according to claim 16, wherein said embedded computer system controls at least one operation within a diagnostics unit.20. A computer system for problem solving, the system having implementation units communicating with the computer system, the system comprising:an input device for providing the primary goal for the task to be performed; a computer coupled to the output of said input device; a memory portion coupled to said computer comprising: a complexity module for configuring a problem statement and predicting expected solver behavior, wherein said complexity module includes means for detecting problem complexity, means for estimating rate of improvement bounds, and means for selecting a complexity related action, wherein said complexity related action comprises selecting at least one member from the group consisting of returning an error, accepting the best result possible for fixed computational resources, adding computational resources, and changing the problem statement; a controllable solving module coupled to said complexity module for determining actual solver behavior; a synthesis module for determining configuration parameter vectors; and comparison means for comparing said actual solver behavior with said expected solver behavior and determining whether a problem solution has been found; and output means for providing a statement of the problem solution. 21. The computer system for problem solving according to claim 20, wherein said problem solver comprises an adaptive constraint problem solver.22. The computer system for problem solving according to claim 20, further comprising a learning module.23. The computer system for problem solving according to claim 20, further comprising a problem transformer module for transforming said problem statement after receiving said problem statement from said input device.24. The computer system for problem solving according to claim 20, wherein said configuration parameters include problem configuration parameters and solver configuration parameters.25. The computer system for problem solving according to claim 24, further comprising a problem transformer module for transforming said problem configuration parameters before providing said problem configuration parameters to said solving module.26. The computer system for problem solving according to claim 20, wherein said complexity module comprises a data structure, said data structure containing configuration parameters and expected behaviors for a plurality of problem types.27. The computer system for problem solving according to claim 20, wherein said control computer comprises an embedded computer system.28. The computer system for problem solving according to claim 27, wherein said embedded computer system controls at least one operation within a copier or printer.29. The computer system for problem solving according to claim 27, wherein said embedded computer system controls at least one operation within a process control system.30. The computer system for problem solving according to claim 27, wherein said embedded computer system controls at least one operation within a diagnostics unit.31. A problem solver in the form of a program to be run on a computer system, said problem salver comprising:means for receiving a problem statement; means for detecting problem complexity; means for estimating rate of improvement bounds; means for selecting a complexity related action, wherein said complexity related action comprises selecting at least one member from the group consisting of returning an error, accepting the best result possible for fixed computational resources, adding computational resources, and changing the problem statement; means for predicting expected solver behavior associated with said problem statement; means for providing configuration parameters for a plurality of problems; means for determining a set of configuration parameter vectors; means for performing a partial search with said configuration parameter vectors; means for calculating actual solver behavior; means for reviewing said actual solver behavior incrementally to determine if a problem solution has been found, wherein reviewing comprises comparing said expected solver behavior to said actual solver behavior; means for determining whether to perform a solver iteration step or to request an adaptation step if a problem solution has not been found; means for performing a solver iteration step, comprising performing another search step, calculating a revised actual solver behavior and determining whether to repeat said solver iteration step; means for comparing said actual solver behavior with said expected solver behavior; means for requesting performance of an adaptation step; means for performing an adaptation step, comprising modifying said configuration parameters, determining a revised expected problem solver behavior, and providing said modified configuration parameters and said revised expected problem solver behavior to said means for performing a solver iteration step; and means for providing the problem solution to an output device. 32. A problem solving method in the form of a program to be run on a computer system comprising:receiving a problem statement; means for detecting problem complexity; configuring a problem solver with configuration parameters; determining a set of configuration parameter vectors; predicting expected solver behavior associated with said configuration parameters for said problem statement; searching for a solution with said configuration parameter vectors; determining actual solver behavior; means for estimating rate of improvement bounds; determining if a problem solution has been found, comprising comparing said expected solver behavior with said actual solver behavior incrementally; means for selecting a complexity related action, wherein said complexity related action comprises selecting at least one member from the group consisting of returning an error, accepting the best result possible for fixed computational resources, adding computational resources, and changing the problem statement; determining whether to perform a solving iteration step or an adaptation step if a problem solution has not been found; performing said solver iteration step, when said solver iteration step is selected, comprising the steps of determining a new actual solver behavior and determining whether to repeat said iteration step; repeating said solver iteration step until said adaptation step is selected; comparing said actual solver behavior with said expected solver behavior when said adaptation step is selected; performing said adaptation step, comprising the steps of modifying said configuration parameters, determining expected solver behavior associated with said modified configuration parameters, determining a revised actual solver behavior, reviewing said revised actual solver behavior to determine if a problem solution has been found, determining whether to perform said solver iteration step or to perform another adaptation step if a problem solution has not been found, and repeating said iteration step until said adaptation step is selected; repeating said adaptation step until a problem solution is found; and transmitting a solution statement. 33. The problem solving method according to claim 32, wherein said problem solving method comprises an adaptive constraint problem solving method.34. The problem solving method according to claim 32, further comprising the step of refining the configuration parameters.35. The problem solving method according to claim 32, further comprising the step of transforming said problem statement.36. The problem solving method according to claim 32, wherein said configuration parameters include problem configuration parameters and solver configuration parameters.37. The problem solving method according to claim 36, further comprising the step of transforming said problem configuration parameters.38. The problem solving method according to claim 32, wherein the step of determining a set of configuration parameter vectors further comprises:choosing a set of default configuration parameter vectors; selecting an initial minimum point; performing a local search; evaluating actual behavior to determine whether to repeat a local search or select a different solver algorithm; repeating a local search with a second minimum point when the step of repeating a local search is selected; and revising the set of configuration parameter vectors for each search performed. 39. The problem solving method according to claim 32, further comprising the step of selecting an algorithm for calculating a problem solution.40. An article of manufacture comprising a computer usable medium having computer readable program code embodied in said medium which, when said program code is executed by said computer causes said computer to perform method steps for problem solving for use in a computer system, wherein the problem solver includes a solving module and a complexity module, said method comprising:receiving a problem statement from the applications module; predicting an expected problem solver behavior associated with configuration parameters for said problem statement; providing the solving module with said configuration parameters; selecting a set of configuration parameter vectors; determining a set of search space points; perform a partial search with said configuration parameter vectors; determining actual solver behavior; reviewing said actual solver behavior incrementally to determine if a problem solution has been found, wherein reviewing comprises comparing said expected solver behavior with said actual solver behavior; determining whether to perform a solver iteration step or to request the complexity module to perform an adaptation step if a problem solution has not been found, wherein said complexity module includes means for detecting problem complexity, means for estimating rate of improvement bounds, and means for selecting a complexity related action, wherein said complexity related action comprises selecting at least one member from the group consisting of returning an error, accepting the best result possible for fixed computational resources, adding computational resources, and changing the problem statement; performing a said solver iteration step when said solver iteration step is selected, comprising the steps of determining new actual solver behavior and determining whether to repeat said solver iteration step; repeating said solver iteration step until said adaptation step is selected; comparing said actual solver behavior with said expected solver behavior when said adaptation step is selected; requesting the complexity module to perform said adaptation step; performing said adaptation step, comprising the steps of modifying said configuration parameters within the complexity module, configuring the solving module with said modified configuration parameters, determining expected solver behavior associated with said modified configuration parameters for said problem statement, selecting an algorithm to calculate a revised problem solution, determining a revised actual solver behavior associated with said modified configuration parameters for said problem statement, reviewing said revised actual solver behavior to determine if a problem solution has been found, determining whether to perform said solver iteration step or to request the complexity module to perform another adaptation step if a problem solution has not been found, and repeating said iteration step until said adaptation step is selected; repeating said adaptation step until a problem solution is found; and providing the solution to the applications module.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (16)
Trif Ioan,CAX ; Trif Niculaie,CAX, Adaptive problem solving method and system.
Crawford ; Jr. James M. ; Kennedy Brian M. ; Lin Tiaohua ; Venkatasubramanyan Narayan ; Kunchithapatham Arun ; Zeithammer Karel,BEX, Computer implemented system and method for high level controlled searching through a problem space.
Gounares Alexander G. ; Spady Stephen W., Method and apparatus for adaptively solving sequential problems in a target system utilizing evolutionary computation techniques.
Kimbel Jeffrey C. (Forest Lake MN) Diamond Marc D. (Inver Grove Heights MN) Ross Stephen E. (Minneapolis MN) Rennolet Charles L. (St. Paul MN), System for parallel implementation of combinatorial optimization in a multiprocessor network for generating search graph.
Master, Paul L.; Hogenauer, Eugene; Scheuermann, Walter J., Adaptive integrated circuitry with heterogeneous and reconfigurable matrices of diverse and adaptive computational units having fixed, application specific computational elements.
Master, Paul L.; Hogenauer, Eugene; Scheuermann, Walter J., Adaptive integrated circuitry with heterogeneous and reconfigurable matrices of diverse and adaptive computational units having fixed, application specific computational elements.
Master, Paul L.; Hogenauer, Eugene; Scheuermann, Walter James, Adaptive integrated circuitry with heterogeneous and reconfigurable matrices of diverse and adaptive computational units having fixed, application specific computational elements.
Master, Paul L.; Hogenauer, Eugene; Scheuermann, Walter James, Adaptive integrated circuitry with heterogenous and reconfigurable matrices of diverse and adaptive computational units having fixed, application specific computational elements.
Master, Paul L.; Hogenauer, Eugene; Scheuermann, Walter James, Adaptive processor for performing an operation with simple and complex units each comprising configurably interconnected heterogeneous elements.
Master, Paul L.; Smith, Stephen J.; Watson, John, Apparatus, method, system and executable module for configuration and operation of adaptive integrated circuitry having fixed, application specific computational elements.
Master, Paul L.; Smith, Stephen J.; Watson, John, Apparatus, method, system and executable module for configuration and operation of adaptive integrated circuitry having fixed, application specific computational elements.
Master, Paul L.; Smith, Stephen J.; Watson, John, Apparatus, method, system and executable module for configuration and operation of adaptive integrated circuitry having fixed, application specific computational elements.
Master, Paul L.; Smith, Stephen J.; Watson, John, Apparatus, system and method for configuration of adaptive integrated circuitry having fixed, application specific computational elements.
Master, Paul L.; Smith, Stephen J.; Watson, John, Apparatus, system and method for configuration of adaptive integrated circuitry having heterogeneous computational elements.
Heidari, Ghobad; Chang, Kuor Hsin; Master, Paul L.; Hogenauer, Eugene B.; Scheuermann, Walter James, Communications module, device, and method for implementing a system acquisition function.
Kropaczek, David Joseph; Karve, Atul Arun; Chopelas, Angelo Peter; Moore, Brian, Method and apparatus for evaluating a proposed solution to a constraint problem for a nuclear reactor involving channel deformation.
Plunkett, Robert T.; Heidari, Ghobad; Master, Paul L., Method and system for managing hardware resources to implement system functions using an adaptive computing architecture.
Plunkett, Robert T.; Heidari, Ghobad; Master, Paul L., Method and system for managing hardware resources to implement system functions using an adaptive computing architecture.
Plunkett, Robert T.; Heidari, Ghobad; Master, Paul L., Method and system for managing hardware resources to implement system functions using an adaptive computing architecture.
Plunkett, Robert T.; Heidari, Ghobad; Master, Paul L., Method and system for managing hardware resources to implement system functions using an adaptive computing architecture.
Mu, Shengjing; Weng, Stephen Wei Hong; Lee, Joseph Ching Hua, Method of model identification for a process with unknown initial conditions in an industrial plant.
Master,Paul L.; Hogenauer,Eugene; Wu,Bicheng William; Chuang,Dan MingLun; Freeman Benson,Bjorn, Method, system and program for developing and scheduling adaptive integrated circuity and corresponding control or configuration information.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.