 |
Claims  |
|
|
What is claimed is:
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.
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 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.
3. 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.
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.
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, 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.
10. 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.
11. 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.
12. 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.
13. 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.
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.
15. 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.
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.
17. 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.
18. 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.
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.
20. 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.
21. 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. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
FIELD OF THE INVENTION
This invention relates generally to systems for solving resource allocation
problems, wherein the ability of the system to provide optimal solutions
to problems of a given class improves over time through simplification of
the decision-making process. More particularly, the invention relates to
methods and systems for solving a wide class of resource allocation
problems, wherein common elements of prior solutions are employed to
simplify computation of successive solutions.
BACKGROUND OF THE INVENTION
For many years, workers have sought improvement in the automated solution
of resource allocation problems. "Resource allocation problems", as used
in this application, encompasses many different classes of problems. For
example, a classical resource allocation problem is the so-called
"traveling salesman" problem, wherein the question is to find the most
efficient route to be taken by a traveling salesman through a series of
stops, for example, all 48 state capitals of the continental United
States. Additional constraints may include that no capital can be visited
more than once, that the trip is to be accomplished using minimum total
mileage, or the like. One way of solving this problem would be to compute
all possible paths and simply to determine which had the least total
mileage. However, as will be appreciated by those of skill in the art,
there are so many possible paths that this problem is computationally very
costly to solve using this "brute force" approach. Accordingly, the art
has sought ways to simplify such problems.
Another class of resource allocation problems relates to the targeting of
specified resources, such as weapons, towards specified goals, such as
targets to be destroyed. The problem takes on additional complexities when
it is realized that the likelihood of success of each weapon with respect
to a particular target must be taken into account. Further, while the most
reliable weapon may initially be targeted to the most important target,
thus requiring evaluation of the relative importance of the targets in
addition to reliability of the weapons, consideration of further
constraints may also be necessary. For example, it may transpire that one
of the targets cannot be successfully attacked other than with a single
most effective weapon, meaning that another target, possibly the most
important, must be attacked with less effective weapons if the overall
solution is to be of value. As individual targets are hit, the relative
priorities of the targets may change, depending on actual success ratios.
A suitable mechanism for solving such a problem must also take into
account multiple targeting of various weapons on the same targets to
ensure their destruction, and other similar constraints. Defensive
considerations must also be accounted for. Again, the "brute-force"
approach of trying all possible solutions in order to select the most
efficient is prohibitively costly in terms of the computation time and
resources necessary.
The prior art has proposed solution of such complex problems using
so-called "neural network" techniques. Neural networks may be considered
to be sets of nodes connected by links, and may be realizable either
physically or in computer software. Decisions are made based on plural
weighted inputs to each node. The advantage of neural networks is
generally considered to be that they "learn" in the sense that in a series
of trials they can improve their performance, gradually approaching the
optimal solution of a given problem. Numerous references describe neural
networks both theoretically and their application to various practical
problems, and additional references provide further improvements thereon.
See generally U.S. Pat. Nos. 5,276,772 to Wang et al, 5,050,095 to Samad,
5,040,134 to Park, 5,222,195 to Alkon et al, and 5,276,771 to Manukian et
al.
However, so far as known to the present inventor, no neural network
solution is entirely satisfactory for solution of resource allocation
problems as generally above, particularly in that the performance of
neural networks degrades steeply when the constraints of a particular
problem deviate from those initially learned by the network. Generally,
performance gains obtained by a neural network's learning a solution to
one problem do not carry over to another problem, requiring the network to
be completely retrained. As resource allocation problems of a given class
vary widely due to changes in the set of available resources, modification
of allocation priorities, and other constraints, neural networks are not
satisfactory for efficient solution of resource allocation problems.
SUMMARY OF THE INVENTION
The present invention addresses these deficiencies of the prior art by
providing a self-adaptive system for solving resource allocation and
similar problems. According to the invention, prior solutions to similar
problems are stored and used in partial solution of later problems. Where
a particular set of allocation decisions is made in a successful solution
to a problem, and the same allocations are useful in solution of a
subsequent problem, that fact is automatically stored. That subset of
allocations can then be replaced by a single more simplified
representation of the group of allocations in subsequent solutions of
problems from the same class of problems, saving on the computation time
required to perform the entire solution.
Taking a very simple example, suppose that in the traveling salesman
problem described above, the salesman must visit all of the 48 capitals of
the contiguous United States while traveling the least total number of
miles. As indicated above, it is computationally inefficient to carry out
all possible solutions to determine the minimal amount of mileage
required. However, in carrying out a number of solutions it may be
apparent that in each case the salesman visits Annapolis, Md., Wilmington,
Del., and Trenton, N.J., in sequence simply because these capitals are so
close to one another. If the United States is represented as a network,
wherein the capitals are represented by the nodes and highways are
represented by links connecting the nodes, according to the invention,
three nodes, representing the three capitals, are replaced by a single
"supernode" in calculation of the complete solution. Simply reducing the
number of possible nodes which must be visited in sequence from 48 to 46
in this way substantially reduces the computation time. Similarly, other
groups of capitals may always be visited in sequence, further simplifying
the calculations. For example, Concord, N.H., Boston, Mass., and Augusta,
Me. would also typically form a single supernode, further simplifying the
computation. When the solution is determined, the supernodes are replaced
by their constituent nodes and links, thus "reconstructing" the network.
In this example, the nodes represent actual points in space, and the links
between them the actual distances therebetween. In other problems, the
nodes may be physical objects, such as weapons having finite probabilities
of success, and the links their allocation to targets; or the nodes may be
intangibles, such as funds, and the links sequences connecting events in
time; or the nodes may be personnel, and the links the time required to
carry out needed work. In each case, a network provides a useful way to
model the choices presented between the various options available.
While the example given above of the traveling salesman problem may seem
trivial, in fact the conventional wisdom in computer programming generally
is to analyze all possible solutions, that is, to rely on the
"brute-force" power of the computer to carry out massive computations in
order to determine optimum solutions to complex problems in resource
allocation. Even with modern "parallel processing" computers, which divide
the computational load between plural processors to solve massive
problems, the computation time required to solve such complex problems is
excessive.
According to an important aspect of the invention, repetitive computations
common to given classes of problems are automatically recognized. A
partial solution, typically derived in solution of one or more prior
problems, is automatically and optimally substituted for the repetitive
computations in arriving at an optimum solution to each subsequent
resource allocation problem. This process may be referred to as
"decomposition" of the network connecting the resources available to the
goals to be satisfied. When the optimum solution has been determined, the
complete network is reconstructed, providing a complete solution to the
problem.
Examples of the use of the invention in reconfiguration of a node system
include power routing in the case of partial grid failure in a power
distribution system, information rerouting in a communication network
connected by communications processors at physically spaced nodes, or
rerouting of goods and the like in a complex transportation system to
compensate for temporary road blockages and the like. In these systems,
the nodular structure of the network connecting the resources to be
allocated to the goals to be satisfied is apparent. However, as indicated
above, the system of the invention has applicability to resource
allocation problems beyond such clearly nodular structures.
Allocation of weapons to targets to be destroyed is a common resource
allocation problem, often involving the assignment of literally thousands
of weapons to hundreds of targets. An optimum solution, or even a
near-optimum solution to a particular problem, cannot be found other than
by extensive modeling. Nonetheless, as indicated above in the case of the
traveling salesman problem, certain partial solutions do appear
repetitively, e.g., in repeated simulations involving likely sets of
resources available and targets to be hit. In subsequent calculations,
those partial solutions known to be effective can be substituted for the
corresponding portion of the complete network, greatly shortening the
computation time required.
In this example, the nodes are physical objects, such as weapons and
targets. There are two types of links: links between weapons and targets,
representing allocation of weapons to different targets weighted by finite
probabilities of success, and links between the weapons themselves,
weighted by the relative frequency of joint allocation of those weapons to
targets in a series of weapon allocation problems. In the latter case, the
strength or "reliability" of "resource-to-resource" links connecting
weapons represent the frequency of allocation of that combination of
weapons to a target. Automatic recognition of such effective joint
allocations, and using this recognition to simplify the actual allocation
process, is at the heart of the present invention.
Specifically, after a sufficient number of resource allocation problems
have been solved, common resource-to-resource connections form a network
having links of varying strength depending on how often those connections
have been exercised, that is, how often each combination of weapons has
been jointly used throughout the history of previous allocations. The
network is then self-partitioned into cohesive clusters, or "packets",
each including those weapons that, according to the accumulated
experience, can usefully be allocated jointly against their targets. The
packets are then replaced with "supernodes" in actual resource allocation.
As a result, the original problem of making allocation decisions with
respect to each weapon individually is dynamically reduced to a much
smaller problem of allocating a few groups of weapons.
Variation in the problem conditions, for example, addition of new weapons,
change of target priorities, and the like entails addition of new nodes to
the network, and/or change of connection weights. The network is then
automatically and optimally repartitioned and new packets of nodes are
formed to accommodate the new circumstances. Preferably, the partitioning
algorithm balances the significance of new circumstances (that is, the
weights of the new connections) against the already existing network
properties, so that the newly computed groups incorporate the old ones in
an optimal fashion. In this way the system builds continuously on its
previous experiences, accommodating changes of conditions without limit
and without performance degradation.
Recognition of repeated sequences of user activities can also be used
according to the invention to simplify processing. For example, the
teachings of the invention can be used in designing man-machine
interfaces, e.g., the complex control panels required for control of
aircraft, nuclear plants, chemical plants, and the like. Information
indicating the items of data the user repetitively accesses and control
actions taken in response to various repetitive sequences of events can be
collected in prototyping the control panel, and used to simplify the user
interface accordingly, for example, to conveniently provide the user those
pieces of information and control options he has commonly requested
previously in similar control situations.
In a further example, presently available computer programs such as word
processing programs or the like typically provide an initial user screen
including a menu prompting the user to select a control option from a
menu, e.g., "File", "Print", "Edit", "View", "Help", and the like. This
initial menu, and a number of sub-menus, are organized in a "tree", such
that when the user selects a control option from one menu, a corresponding
sub-menu appears, giving the user a new selection of options. These menus,
and the sequence in which the various choices appears are selected by the
system designer in accordance with his understanding of how the typical
user will want to operate the system, i.e., in accordance with the system
designer's best guess of likely operational sequences, so as to maximize
convenience to the user.
In many circumstances, however, the user may have a different idea of how
the computer program should be organized; that is, the user's idea of the
appropriate items to appear on each menu may differ from the system
designer's, in which case the user will commonly spend much time looking
for various control options. Of course, the user can consult the manual
and find the option he is looking for; however, it will be apparent that
most users do not care to do so, and certainly do not care to do so more
than once. Accordingly, it would be desirable if the program itself would
monitor the sequence in which the user accessed various control options,
and would adapt itself, and specifically its sequence of menus, so that
the control options previously sought by the user would be subsequently
presented by menus so as to allow the same sequence used previously to be
conveniently followed. Accordingly, this also is within the scope of the
invention.
In one embodiment of a system according to the invention, it may be
configured as a long-term memory having self-organizing associative
capabilities, effectively connecting nodes by links, a short-term memory
where on-line resource allocation decisions are made based on the resource
associations established off-line in the long-term memory, and a
supervisory and interaction management module providing operator
interaction and control functions.
The short-term memory performs the actual allocations, based on the network
output, and can provide near optimal allocation, e.g., by applying the
solution of the most similarly prior problem to a new problem. The
long-term memory carries out the detailed computations required to
identify packets and carry out decomposition of the network. Over time, as
the long-term memory becomes more and more efficient due to simplification
of the decision tree by recalling previously successful partial solutions,
the capability of the short-term memory grows concomitantly greater.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention will be better understood if reference is made to the
accompanying drawings, in which:
FIG. 1 shows a two-dimensional matrix of the type commo | | |
