US5586219A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Probabilistic resource allocation system with self-adaptive capability
Assignee: National Aeronautics and Space Administration
•
Filing: 1994-09-30
•
Granted: 1996-12-17
•
Expires: 2014-09-30
Abstract
Abstract A probabilistic resource allocation system is disclosed containing a low capacity computational module (Short Term Memory or STM) and a self-organizing associative network (Long Term Memory or LTM) where nodes represent elementary resources, terminal end nodes represent goals, and directed links represent the order of resource association in different allocation episodes. Goals and their priorities are indicated by the user, and allocation decisions are made in the STM, while candidate associations of resources are supplied by the LTM based on the association strength (reliability). Reliability values are automatically assigned to the network links based on the frequency and relative success of exercising those links in the previous allocation decisions. Accumulation of allocation history in the form of an associative network in the LTM reduces computational demands on subsequent allocations. For this purpose, the network automatically partitions itself into strongly associated high reliability packets, allowing fast approximate computation and display of allocation solutions satisfying the overall reliability and other user-imposed constraints. System performance improves in time due to modification of network parameters and partitioning criteria based on the performance feedback.
Inventors
- 👤 Yan M. Yufik
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 20:16
CPC Classifications
G; G06; G06N; G06N3/00; G06N3/02; G06N3/04; G06N3/047; G06N3/0495; G06N3/08; G06N3/082; G06N3/09; G06Q; G06Q10/00; G06Q10/04; G06Q10/047; G06Q10/06
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
284 words
A self-adaptive system for providing progressively improved solutions to successive examples of a class of generally similar problems of resource allocation, comprising: a supervisory and interaction management module (SIMM) for receiving input data describing the goals to be met in solution of, and the resources available to solve, a particular problem; a short-term memory (STM) for receiving said input data from said SIMM, for receiving a list of candidate resources from long-term memory, and for comparing the input data to the candidate resources to determine a near-optimal resource allocation; a long-term memory (LTM) maintaining a list of candidate resources and associated probabilities of goal satisfaction, said LTM being effectively implemented as a reconfigurable network of nodes connected to neighboring nodes by links, each node representing a step in a pathway connecting one or more resources to one or more goals, means for computing alternate pathways between the nodes of the network in order to allocate resources to goals in deriving candidate solutions of each particular problem of said class of problems, and for evaluating the relative efficiency of each of the alternate pathways thus computed in order to determine an optimum solution for that particular problem with respect to the present configuration of the network; means for identifying common groups of nodes connected by links employed in the optimum solutions of plural examples of problems from a given class of problems; and means for effectively decomposing said network by replacing said identified common groups of nodes connected by links with fewer nodes connected by fewer links to one another, or to the nodes previously connected to the identified common group of nodes, for subsequent solution of further problems from said given class of problems.
Claim 2
Dependent Claim
284 words
A self-adaptive system for providing progressively improved solutions to successive examples of a class of generally similar problems of resource allocation, comprising: a supervisory and interaction management module (SIMM) for receiving input data describing the goals to be met in solution of, and the resources available to solve, a particular problem; a short-term memory (STM) for receiving said input data from said SIMM, for receiving a list of candidate resources from long-term memory, and for comparing the input data to the candidate resources to determine a near-optimal resource allocation; a long-term memory (LTM) maintaining a list of candidate resources and associated probabilities of goal satisfaction, said LTM being effectively implemented as a reconfigurable network of nodes connected to neighboring nodes by links, each node representing a step in a pathway connecting one or more resources to one or more goals, means for computing alternate pathways between the nodes of the network in order to allocate resources to goals in deriving candidate solutions of each particular problem of said class of problems, and for evaluating the relative efficiency of each of the alternate pathways thus computed in order to determine an optimum solution for that particular problem with respect to the present configuration of the network; means for identifying common groups of nodes connected by links employed in the optimum solutions of plural examples of problems from a given class of problems; and means for effectively decomposing said network by replacing said identified common groups of nodes connected by links with fewer nodes connected by fewer links to one another, or to the nodes previously connected to the identified common group of nodes, for subsequent solution of further problems from said given class of problems.
Claim 3
Dependent Claim
69 words
The system of claim 1, wherein said means for identifying common groups of nodes connected by links employed in the optimum solutions of plural examples of problems from a given class of problems comprises means for maintaining a record of the frequency of use of each of the links connecting nodes in the network in the optimum solutions of successive examples of problems from a given class of problems.
Claim 4
Dependent Claim
118 words
The system of claim 2, wherein said means for identifying common groups of nodes connected by links employed in the optimum solutions of plural examples of problems from a given class of problems identifies said common groups by successively assigning groups of nodes to packets, comparing the frequency of use of the links internal to each of the packets to those connecting the nodes of each packet to nodes outside each packet, and treating the nodes of the packet as an identified common group of nodes when the frequency of use of the links internal to the packet exceeds the frequency of use of the links connecting the nodes internal to the packet to nodes outside the packet.
Claim 5
Dependent Claim
29 words
The system of claim 1, further comprising means for returning the network to its original configuration prior to carrying out resource allocation according to the optimum solution thus derived.
Claim 6
Dependent Claim
54 words
The system of claim 1, wherein said fewer nodes connected by fewer links to the nodes previously connected to the identified common group of nodes employed to replace each identified common group of nodes comprises a single node connected by links with all nodes to which the identified common group of nodes was connected.
Claim 7
Dependent Claim
56 words
The system of claim 1, further comprising means for storing the network configuration after identification of a group of common nodes in solution of a particular problem, and means for subsequent decomposition of the network to implement the stored configuration responsive to indication that a problem from the same class of problems is to be solved.
Claim 8
Independent Claim
251 words
A method for increasingly efficient solution of a series of problems from a class of problems requiring allocation of resources to a plurality of goals, comprising the steps of: defining a reconfigurable network of nodes connected by links, each node effectively representing a step in allocating given resources to given goals; carrying out the following steps in solution of a particular problem: computing alternate pathways between the nodes of the network in order to allocate resources to goals in solution of each particular problem of said class of problems; and evaluating the relative efficiency of each of the alternate pathways thus computed, in order to determine an optimum solution for that particular problem with respect to the present configuration of the network; and carrying out the following steps after reaching an optimum solution for a particular problem with respect to the present configuration of the network: comparing the sets of nodes employed by the optimum solution to similar sets of nodes employed in the optimum solutions of other problems of the same class of problems; determining whether common groups of nodes are employed substantially similarly in the optimum solutions of plural problems from a given class of problems; and if such common groups of nodes are identified, reconfiguring the network for increased efficiency in subsequent solution of problems from the same class of problems, by replacing said identified common groups of nodes with fewer nodes connected to one another, or to the nodes connected to the replaced common groups of nodes.
Claim 9
Independent Claim
251 words
A method for increasingly efficient solution of a series of problems from a class of problems requiring allocation of resources to a plurality of goals, comprising the steps of: defining a reconfigurable network of nodes connected by links, each node effectively representing a step in allocating given resources to given goals; carrying out the following steps in solution of a particular problem: computing alternate pathways between the nodes of the network in order to allocate resources to goals in solution of each particular problem of said class of problems; and evaluating the relative efficiency of each of the alternate pathways thus computed, in order to determine an optimum solution for that particular problem with respect to the present configuration of the network; and carrying out the following steps after reaching an optimum solution for a particular problem with respect to the present configuration of the network: comparing the sets of nodes employed by the optimum solution to similar sets of nodes employed in the optimum solutions of other problems of the same class of problems; determining whether common groups of nodes are employed substantially similarly in the optimum solutions of plural problems from a given class of problems; and if such common groups of nodes are identified, reconfiguring the network for increased efficiency in subsequent solution of problems from the same class of problems, by replacing said identified common groups of nodes with fewer nodes connected to one another, or to the nodes connected to the replaced common groups of nodes.
Claim 10
Dependent Claim
29 words
The method of claim 7, wherein said identified common groups of nodes are replaced by single nodes connected to the nodes connected to the replaced common group of nodes.
Claim 11
Dependent Claim
68 words
The method of claim 7, wherein said step of determining whether common groups of nodes are employed substantially similarly in the optimum solutions of plural problems from a given class of problems is performed by maintaining a record of the frequency of use of each of the links connecting nodes in the network in the optimum solutions of successive examples of problems from a given class of problems.
Claim 12
Dependent Claim
115 words
The method of claim 7, wherein said step of determining whether common groups of nodes are employed substantially similarly in the optimum solutions of plural problems from a given class of problems is performed by successively assigning groups of nodes to packets, comparing the frequency of use of the links internal to each of the packets to those connecting the nodes of each packet to nodes outside each packet, and treating the nodes of the packet as an identified common group of nodes when the frequency of use of the links internal to the packet exceeds the frequency of use of the links connecting the nodes internal to the packet to nodes outside the packet.
Claim 13
Dependent Claim
55 words
The method of claim 7, comprising the further steps of storing the network configuration responsive to identification of a group of common nodes in solution of a particular problem, and decomposing the network responsive to the stored configuration responsive to indication that a problem from the same class of problems is subsequently to be solved.
Claim 14
Dependent Claim
53 words
The method of claim 7, comprising the further steps of calculating a gain component with respect to each node assigned to an alternate pathway connecting one or more resources to goals, and evaluating the relative efficiency of each pathway as a sum of said gain components of all nodes employed in said pathway.
Claim 15
Dependent Claim
27 words
The method of claim 12, wherein said step of calculating the gain component with respect to each node is performed responsive to a transaction cost assigned thereto.
Claim 16
Independent Claim
200 words
A method of reconfiguring an adaptive user interface responsive to patterns of use, said interface comprising user information display means and a plurality of user input means, said user input means permitting the user to select from among control options provided as linked sequences of control options and displayed for user selection on display means, comprising the steps of: modeling the linked sequences of control options as a network of nodes connected by links, wherein the nodes are control options and the links are associations between respective control options, said associations including both user-selected sequences of control options and predetermined linked sequences of control options, wherein linked sequences of control options are represented as packets of highly-connected nodes; displaying said linked sequences of control options corresponding to said packets of highly-connected nodes as menus of control options; monitoring user patterns of selection of control options, in order to identify commonly-selected control options; and adding said commonly-selected control options to said displayed linked sequences of control options corresponding to said packets of highly-connected nodes; thereby reconfiguring the display of menus of control options responsive to the sequence of selection of specific control options by the user as said interface is used.
Claim 17
Independent Claim
200 words
A method of reconfiguring an adaptive user interface responsive to patterns of use, said interface comprising user information display means and a plurality of user input means, said user input means permitting the user to select from among control options provided as linked sequences of control options and displayed for user selection on display means, comprising the steps of: modeling the linked sequences of control options as a network of nodes connected by links, wherein the nodes are control options and the links are associations between respective control options, said associations including both user-selected sequences of control options and predetermined linked sequences of control options, wherein linked sequences of control options are represented as packets of highly-connected nodes; displaying said linked sequences of control options corresponding to said packets of highly-connected nodes as menus of control options; monitoring user patterns of selection of control options, in order to identify commonly-selected control options; and adding said commonly-selected control options to said displayed linked sequences of control options corresponding to said packets of highly-connected nodes; thereby reconfiguring the display of menus of control options responsive to the sequence of selection of specific control options by the user as said interface is used.
Claim 18
Dependent Claim
235 words
The method of claim 14, wherein said steps of displaying said linked sequences of control options corresponding to said packets of highly-connected nodes as menus of control options; monitoring user patterns of selection of control options, in order to identify commonly-selected control options; adding said commonly-selected control options to said displayed linked sequences of control options corresponding to said packets of highly-connected nodes; and thereby reconfiguring the display of menus of control options responsive to their selection by the user comprise the steps of: providing a nominal tree structure of menus of said control options, said menus of said tree being linked such that selection of a control option from a given menu accesses a further menu; displaying a menu of available control options on said display means at all times when user input is possible; prompting the user to select control options from the menu displayed, while permitting the selection of other control options; accepting user input indicating selection of a particular control option from a particular menu displayed, and providing an appropriate linked menu in response thereto; accepting user input indicating selection of a particular control option other than from the particular menu displayed, and further recording the control option selected by the user with respect to the particular menu; and adding each control option selected by the user to the menu displayed at its time of selection if not already included therein.
Claim 19
Dependent Claim
250 words
A self-adaptive system for providing progressively improved solutions to successive examples of a class of generally similar problems of resource allocation, comprising: means for maintaining a complete list of candidate resources and associated probabilities of goal satisfaction, said means for maintaining being effectively implemented as a reconfigurable network of nodes connected to neighboring nodes by links, each node representing a step in a pathway connecting one or more resources to one or more goals; means for accepting input data describing the goals to be met in solution of, and the resources available to solve, a particular problem, and for supplying said input data to said means for maintaining; means for computing alternate pathways between the nodes of the network in order to allocate resources to goals in solution of each particular problem of said class of problems, and for evaluating the relative efficiency of each of the alternate pathways thus computed in order to determine an optimum solution for that particular problem with respect to the present configuration of the network; means for identifying common groups of nodes connected by links employed in the optimum solutions of plural examples of problems from a given class of problems; and means for effectively reconfiguring said network by replacing said identified common groups of nodes connected by links with fewer nodes connected by fewer links to one another, or to the nodes previously connected to the identified common group of nodes, for subsequent solution of further problems from said given class of problems.
Claim 20
Dependent Claim
250 words
A self-adaptive system for providing progressively improved solutions to successive examples of a class of generally similar problems of resource allocation, comprising: means for maintaining a complete list of candidate resources and associated probabilities of goal satisfaction, said means for maintaining being effectively implemented as a reconfigurable network of nodes connected to neighboring nodes by links, each node representing a step in a pathway connecting one or more resources to one or more goals; means for accepting input data describing the goals to be met in solution of, and the resources available to solve, a particular problem, and for supplying said input data to said means for maintaining; means for computing alternate pathways between the nodes of the network in order to allocate resources to goals in solution of each particular problem of said class of problems, and for evaluating the relative efficiency of each of the alternate pathways thus computed in order to determine an optimum solution for that particular problem with respect to the present configuration of the network; means for identifying common groups of nodes connected by links employed in the optimum solutions of plural examples of problems from a given class of problems; and means for effectively reconfiguring said network by replacing said identified common groups of nodes connected by links with fewer nodes connected by fewer links to one another, or to the nodes previously connected to the identified common group of nodes, for subsequent solution of further problems from said given class of problems.
Claim 21
Dependent Claim
64 words
The system of claim 16, wherein said means for accepting input data comprises means for receiving a list of candidate resources from said means for maintaining, and for comparing the input data to a limited set of the candidate resources to determine a near-optimal resource allocation, supplied to said means for computing alternate pathways between the nodes of the network as an initial solution.
Claim 22
Dependent Claim
44 words
The system of claim 16, wherein each of said nodes comprises means for evaluating the probability of success of satisfying a particular goal by allocation of resources thereto, such that said network of nodes comprises an element of said means for computing alternate pathways.
Claim 23
Independent Claim
113 words
A method for modularizing and reducing the size of a network of computational nodes connected by links, said network being employed in solution of successive similar problems, comprising the steps of: storing information describing the connection of nodes by links in solution of successive problems; assigning groups of nodes and connecting links to candidate packets; evaluating the relative frequency of use of the links of particular packets in solution of successive problems with respect to the frequency of use of the links connecting the packets to one another, and to the remainder of the network; and replacing commonly-used packets with nodes connected by links to the nodes connected to the packets thus replaced.
Claim 24
Independent Claim
113 words
A method for modularizing and reducing the size of a network of computational nodes connected by links, said network being employed in solution of successive similar problems, comprising the steps of: storing information describing the connection of nodes by links in solution of successive problems; assigning groups of nodes and connecting links to candidate packets; evaluating the relative frequency of use of the links of particular packets in solution of successive problems with respect to the frequency of use of the links connecting the packets to one another, and to the remainder of the network; and replacing commonly-used packets with nodes connected by links to the nodes connected to the packets thus replaced.
Claim 25
Dependent Claim
36 words
The method of claim 19, wherein the average frequency of use of the links of the candidate packets is compared to the average frequency of use of links outside said candidate packets in said evaluating step.
Claim 26
Dependent Claim
36 words
The method of claim 19, wherein the total frequency of use of the links of the candidate packets is compared to the total frequency of use of links outside said candidate packets in said evaluating step.
References Cited (Backward Citations)
US4797839A
Cited
US4525830A
Cited
US4748658A
Cited
US5043876A
Cited
US5050095A
Cited
US5222195A
Cited
US5040134A
Cited
US5148365A
Cited
US5050096A
Cited
US5046019A
Cited
US5343388A
Cited
US5276772A
Cited
US5325525A
Cited
US5440675A
Cited
US5369570A
Cited
US5276771A
Cited
US5446891A
Cited
US5402478A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-17 | 2000-06-17 | 2000-12-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-17 | 2004-06-17 | 2004-12-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-17 | 2008-06-17 | 2008-12-17 | $7700.00 | Window Closed / Lapsed |