Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-06-07
2004-05-11
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06735596
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
Not applicable
FEDERALLY SPONSORED RESEARCH
Not applicable
MICROFICHE APPENDIX
Not applicable
FIELD OF THE INVENTION
The present invention relates generally to computerized methods for analyzing and solving decision problems, for globally optimizing the operation of systems and processes, and for designing graphical user interfaces. More specifically, the invention provides software methods and a graphical user interface for solving decision and system optimization problems involving sequential, probabilistic and multi-objective decisions.
BACKGROUND OF THE INVENTION
Introduction
Artificial Intelligence (AI) may be defined as the art of creating methods and machines for performing functions requiring various forms and degrees of natural intelligence when attempted by humans. Considerable advances have been made since the late 1970s by computer scientists, operations researchers and system scientists in applying the results of AI research to the construction of computational tools for automating various processes in the art of decision making and risk analysis [14, 17]. Such advances have been especially successful in the field of Decision Analysis, where mathematical and statistical modeling methods have been combined with computational techniques to develop new tools to assist Decision Makers in selecting an optimal choice from a plurality of choices [1-3, 9, 19-30, 56].
While there is no unique method for solving complex decision problems, the flowchart of
FIG. 1
illustrates the major steps currently guiding decision analysts. Software developers have implemented these steps in a variety of ways, and important technical terms have received different descriptions throughout the literature. To distinguish the invention disclosed herein from the current art, a precise definition of some critical terms of art is needed.
Technical Definitions
Concepts From Graph Theory
A graph G=(N, E) consists of a set N={n
1
, n
2
, . . . } of nodes and a set E ⊂ N×N of edges or arcs. For any edge e=(u, v) in E, we say that nodes u an v are adjacent. When (u, v) is an ordered pair, it is a directed edge, where u is adjacent to v and v is adjacent from u, u is called the parent of v and v is called the child of or offspring of u. When every edge in G is an ordered pair, G is called a directed graph, or digraph.
A path in G from v
1
to v
k
is a sequence <(v
1
, v
2
), (v
2
, v
3
), . . . , (v
k−2
, v
k−1
), (v
k−1
, v
k
)> of adjacent edges, sometimes written <v
1
, v
2
, . . . , v
k
>, where each node is distinct, except possibly for v
1
=v
k
, in which case the path is called closed, and said to constitute a cycle or circuit. Otherwise the path is called open.
A node w in N is said to be isolated if there does not exist an edge (u, v) in E for which either w=u or w=v. A node is called a root of G if there are paths from u to every other node in G. A graph G is connected if, for every pair (u, v) of nodes in N, there exists a path from u to v or from v to u. A graph H=(M, D) is a sub-graph of G=(N, E) if M⊂N and D⊂E. In a subgraph H of G, a node w in M is called a root in G if w is a root of H. Whenever there exists a path from a node u to another node v in a directed graph G, v is a descendant of u and u is an ancestor of v.
A graph G is a tree if there exists exactly one path between any two distinct nodes of G. A directed graph G is a directed tree, tree for short, if G has a root r and there exists exactly one directed path from r to every other node of G. When a graph G is a tree, any sub-graph of G is also a tree, a sub-tree of G. In a tree, every node has at most one parent, and whenever a tree has a unique root, it is called a rooted tree. A node u in a tree G is a leaf node or terminal node if u has no offspring, and similarly for any sub-tree H of G.
Hierarchies
A hierarchical graph with P levels is an object HG=(N, E, H), where
1. (N, E) is a directed and rooted tree
2. H=<H
1
, H
2
, . . . , H
p
>, an ordered partition of N, i.e.
(i) ∪H
i
=N and H
i
∩H
j
=&phgr;, for i and j from l to P, i≈j, and
(ii) for every edge e=(u,v) in E, if u is in H
i
and v is in H
j
, then i>j.
For any partition element H
i
, a node in H
i
is a node at level i. For any edge (u, v) in E, u is superior to v and v is subordinate to u if, and only if, u is in H
i
, v is in H
i
and i>j.
An important application of hierarchical graphs arises when decision problems are motivated by a multiplicity of competing objectives. An objective is a statement of action whose purpose is to attain a desired state or condition. Whenever the nodes of a hierarchical graph represent objectives, the graph is called an objectives hierarchy. Statements such as “minimize losses”, “maximize profit”, “increase reliability” and “reduce environmental risks” are examples of objectives associated with typical decision problems. For any edge (u,v) in E, if u and v are objectives, if u belongs to H
1
and v belongs to H
j
and i>j, then u is the super-objective of v and v is a sub-objective of u, and similarly when i<j.
Semantics of Graphs, Trees and Hierarchies
The terms introduced in the previous sections are used to define graphical and mathematical relationships between nodes, edges and levels. These are topological relationships and, taken collectively, they constitute the topology of the defined graph, tree or hierarchy.
When used as models of some reality, these constructs must be assigned some meaning. This is accomplished by adding another descriptive layer called the semantic layer, where a contextual meaning is attached to the nodes, edges and levels. To illustrate this combination of topology and semantics, consider now a modeling construct that will serve as a basic building block for this disclosure.
Probalistic Decision Trees
A Probabilistic Decision Tree (PDT) is a model of a decision problem that represents all the choices, consequences and paths that a decision maker may experience through time. In very general terms, the major purpose for building and solving a PDT is to find choices that satisfy a decision maker's definition of “optimal”. Another purpose is to evaluate the consequences and collateral risks resulting from the implementation of a given choice, optimal or not. Throughout this disclosure, risk is defined as the numerical value resulting from a finite summation R=&Sgr;(p
i
*c
i
) of product pairs (p
i
*c
i
), where the c
i
s constitute a collection of mutually exclusive and exhaustive events and, for every i, p
i
is the probability of occurrence of c
i
. When a decision maker faces a plurality of choices and uses risk as an optimization criterion, his or her optimal choice is the choice whose selection minimizes risk.
While the c
i
terms are often interpreted as the occurrence of some cost or penalty, no such restrictions apply here, and they may assume any scalar value, positive or negative. Since R has the same form as the expectation operator in the theory of probability and statistics, it is often called the “Expected Risk” and, when R is negative, the “Expected Benefit”.
The topological structure of a PDT is a directed (and rooted) tree whose nodes are of three types, decision nodes, chance nodes and terminal nodes. Referring to
FIG. 3
, a decision node
4
, drawn as a square, represents a decision to be made. A chance node
5
, drawn as a circle, represents a random chance variable, and a terminal node
6
, drawn as a vertical ellipse, represents a leaf in the tree. An offspring
8
of a decision node
4
is a choice available at that node, and an offspring
9
of a chance node
5
is a consequence or outcome associated with the chance node. The offspring of every chance node constitute a mutually exclusive and exhaustive set of consequences or outcomes. Edges relating a node to its offspring are occasionally referred to as branches.
While it usual
Mofiz Apu M
Rones Charles
LandOfFree
Computer method and user interface for decision analysis and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer method and user interface for decision analysis and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer method and user interface for decision analysis and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3187290