Probabilistic resource allocation system with self-adaptive capability
First Claim
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
79 Citations
21 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. 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. - View Dependent Claims (8, 9, 10, 11, 12, 13)
-
-
14. 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. - View Dependent Claims (15)
-
-
16. 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. - View Dependent Claims (17, 18)
-
-
19. 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. - View Dependent Claims (20, 21)
-
Specification