Probabilistic resource allocation system with self-adaptive capability

• US 5,794,224 A
• Filed: 09/29/1995
• Issued: 08/11/1998
• Est. Priority Date: 09/30/1994
• Status: Expired due to Term

• Current Assignee: Yan M. Yufik
• Original Assignee: Yan M. Yufik
• Inventors: Yufik, Yan M.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/536,789
• Time in Patent Office: 1,047 Days
• Field of Search: 395/20, 395/140, 395/27, 395/617, 395/3, 395/23, 395/22, 395/24, 395/650, 395/600, 370/219, 370/221, 364/554, 364/402, 364/401, 706/14
• US Class Current: 706/14
• CPC Class Codes: G06N 3/047 Probabilistic or stochastic networks
• CPC Class Codes: G06N 3/082 modifying the architecture, e.g. adding, deleting or silencing nodes or connections
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

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 weighted 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). Weights 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.

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 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 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.

2. 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 identifies said common groups by successively assigning groups of nodes to packets, comparing the aggregate weight of the links internal to each of the packets to the aggregate weight of the links 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 aggregate weight of the links internal to the packet exceeds that of the links connecting the nodes internal to the packet to nodes outside the packet.

3. The system of claim 1, wherein weights are assigned to links responsive to the frequency of use of each of the links in optimum solutions of successive examples of problems from a given class of problems.

4. 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.

5. 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.

6. 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.

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,

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 aggregate weight of weighted links internal to each of the packets to the aggregate weight of the links 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 aggregate weight of the links internal to the packet exceeds the aggregate weight of the links connecting the nodes internal to the packet to nodes outside the packet.

8. 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.

9. The method of claim 7, comprising the further step of assigning weights to links responsive to evaluation of the comparative 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.

10. 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.

11. 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.

12. The method of claim 11, wherein said step of calculating the gain component with respect to each node is performed responsive to a transaction cost assigned thereto.

13. 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 on display means, comprising the steps of monitoring user patterns of selection of control options, and reconfiguring the display of control options responsive to their selection by the user to group options or sequences of options selected repetitively, in predetermined areas of said display as said interface is used.

14. The method of claim 13, wherein said step of reconfiguring the display of control options responsive to their selection by the user comprises 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.

15. 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 weighted connecting links to candidate packets;

evaluating the stability σ

of candidate packets as σ

=(Σ

W_internal)/(Σ

W_external), where Σ

W_internal is the aggregate weight of the links of a particular candidate packet and σ

W_external is the aggregate weight of the links connecting the candidate packet to other nodes in the network; and

replacing candidate packets as to which σ

exceeds a threshold value with single nodes connected by links to the nodes connected to the packets thus replaced.

16. The method of claim 15, wherein the weight of each link of the candidate packets is evaluated responsive to the average frequency of use of said link.

17. The method of claim 16, 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.

18. A method for reducing the computation time necessary to calculate solutions of network optimization problems using a specified algorithm for determination of optimal solutions, comprising the steps of:

(1) defining a virtual network, comprising a plurality of nodes connected by weighted links, wherein said nodes each represent a resource to be utilized;

(2) providing an initial partition of said network into components each consisting of a number of proposed packets, said proposed packets each comprising a number of said nodes connected by weighted links, and said proposed packets being connected to one another by cutsets, comprising further sets of weighted links, wherein the sum of the weights of the links connecting the nodes of each proposed packet exceed the total weights of the links of the corresponding cutset;

(3) evaluating the stability of the partitioned network by;

(a) determining sums of the weights assigned to the links of each of the proposed packets, and of the corresponding cutsets;

(b) evaluating the stability of the partitioned network by comparing the sum of the weights of the links of each proposed packet to the sum of weight of the links of the corresponding cutset;

(c) repartitioning said networks into a differing set of proposed packets and reevaluating the stability of the repartitioned network; and

(d) repeating said steps (a)-(c) until no further increase in the stability of the packets is identified; and

then

(4) employing said specified algorithm to determine an optimal solution for said partitioned network, treating said packets as single nodes in implementation of said algorithm.

19. The method of claim 18, comprising the further steps of redividing said network into differently allocated components, and performing said steps (3)(a)-(d) prior to reperforming said step (4).

20. The method of claim 18, wherein said virtual network simulates a communication network, and said weights of links are determined by monitoring the frequency of utilization of corresponding physical links in said communication network.

21. The method of claim 18, wherein said virtual network simulates operation of a multifunction display employed by a user in control of a complex device, wherein said nodes in said virtual network correspond to data items monitored or control devices operated by said user in control of said complex device, said packets corresponding to information simultaneously displayed on said display relating to data items monitored or control options available, and wherein said weights of links are determined by monitoring the frequency of access to or control of corresponding physical elements of said complex device.

22. The method of claim 21, wherein said complex device is an aircraft, and said data items monitored include one or more of fuel system status indicators, navigational information, and weapons status, and said control devices operated include one or more of fuel distribution systems, communication systems, and weapons control.

23. The method of claim 21, wherein said complex device is an industrial or power plant, said data items include process variables monitored, and said control devices operated include process control elements.

24. The method of claim 21, wherein the cutsets of links connecting packets correspond to the relational sequence of displays of related information or control sequences presented to the user.