Registers – Systems controlled by data bearing records – Credit or identification card systems
Reexamination Certificate
1999-09-27
2003-05-27
Le, Thien M. (Department: 2786)
Registers
Systems controlled by data bearing records
Credit or identification card systems
C235S375000
Reexamination Certificate
active
06568592
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to use of control circuits using various partitionable physical properties to convey information. More particularly, the present invention relates to selective distribution and partitioning of pressure, thermal, chemical, acoustic, or other physical properties as part of a market allocation system for control and coordination of large numbers of actuators and sensors.
BACKGROUND OF THE INVENTION
Market based control requires allocating a task (e.g. physical actuation) among a large number of producers, with each producer bidding for part of the task. The task is determined by consumer agents in the system (higher level controllers or external requirements). Each producer has a supply curve reflecting the actuation or control produced as a function of price and each consumer has a demand curve indicating the actuation needed as a function of price. The equilibrium price is determined by the price at which aggregate demand and aggregate supply are equal. The price in turn determines what each individual actuator produces and individual consumer uses such that the total actuation equals the demanded actuation. As the task changes, different combinations of producers combine to collectively accomplish the task. Such a market is robust against failure of individual agents and changes in tasks, while requiring communication of only one quantity, namely the price, in order to coordinate the actions of an arbitrary and even time varying number of producers. Advantageously, such a price based market system naturally provides a Pareto optimal solution that is near optimal allocation within a degenerate array, even though is the full optimization problem NP-complete. Furthermore, reconciling conflicting goals is readily accomplished by having each individual actuator or consumer individually weight the conflicting goals. The market produces a group resolution between conflicting goals.
Unfortunately, presently available implementation schemes for market based control are impractical and scale poorly for large numbers of producers or consumers, especially when systems requiring real time actuation are considered. One could imagine, for example, connecting the producers and consumers using a bus (e.g. CAN bus, SPI, I
2
C or Ethernet bus) to communicate pricing information. For example, a 10 Mbit Ethernet system could be used to control 10
3
nodes of producers and consumers. Even using readily available off-the-shelf hardware, such a market control system is quite expensive, with per connection node costs of about $10 US dollars, for a total cost on the order of $10,000 US dollars. Moreover, due to the long packet header required, the bus would take on the order of 1-10 &mgr;sec to transmit a 10 bit number to each node, and then the same time to transmit the results back to each agent for one cycle of the market equilibration loop. If there are such 10
3
nodes, this would take on the order 2-20 msecs in the best case without packet collisions. Other widely available buses (e.g. CAN or SPI) would take at least an order of magnitude longer. The problem is even worse if multiple markets for competing allocations are required. For example, in object motion control both torques and forces must be allocated even though the requirements for each may conflict. If one had 10 markets to compute the supply and demand curves of competing allocations, either one would require 10 buses or the process would take on the order of seconds. There also is the issue of synchronizing the processors if a synchronous communication scheme is used.
In contrast to conventional digital control schemes, the present invention uses a high speed analog system minimally requiring only a single line (i.e. a “market wire”) interconnecting multiple producers and consumers in a given market. Analog electronic versions of markets allocate tasks such as actuation or control in a multi-producer and consumer system using correspondences set up between current and the quantity of a commodity and between the voltage and the price. The market consists of consumers removing current from a wire and producers adding current to the wire. The price is the voltage on the wire that eventually reaches an equilibrium price. This voltage, analogous to the equilibrium price, determines the current and hence the actuation produced by each actuator. As in the case of markets, the performance of the system is robust against failures and changes in actuators ortasks.
In one version of an analog system in accordance with the present invention, each consumer has a demand curve that decreases linearly as the voltage on the market wire increases and each producer, such as an actuator or controller, draws current from the wire that serves as the ‘market’. The conductances determine the slopes of the supply and demand curves as well as the market voltage. If some producers produce less, for example, actuation, less current is removed from the wire, the voltage rises causing more actuation from the remaining producers and reduces the demand by the consumers. Conversely, a decrease in demand (smaller conductances) causes less current to be added to the wire causing the market wire voltage to decrease. Production therefore decreases, and demand by the other consumers increases.
Implementation of the foregoing control schemes is of particular utility for problems requiring a large number of actuators to produce a desired actuation level. In this case there would be one consumer with a flat demand curve, i.e., a current source, for which the current(demand) does not change with voltage (price). The actuators (producer agents) would produce actuation such that all this current is removed to ground (demand balanced by supply). This high bandwidth, asynchronous coordination occurs through one wire and can be inexpensive per connection (only a few chips per node). No explicit computation is required to allocate the resources and a near optimal solution is obtained from a possibly degenerate set of equivalent solutions.
Advantageously, like traditional economic markets, analog circuit implementations of the present invention are robust against changes in actuator function or failures. As the cost per unit functionality of sensors, actuators, and computers (agents) continues to decrease, control systems comprised of many interconnected elements become increasingly practical. High speed systems having 10
3
processors with 10 market wires connected with multiplexed A/D's and D/A's or multiple op amp packages operating in real time are economically feasible using apparatus and methods of the present invention. Such systems could be much more responsive to events in their environment and internal states as well as exhibit robustness against component failure. Such an analog electronic implementation is distributed, flexible, easily extensible, efficiently uses wires, and reduces the communication load. Analog markets that can compute weighted sums of up to 10
4
spatially distributed agents and communicate the resulting sum back to agents in about 1-10 &mgr;secs are supportable. The complexity of each such node is about 1-3 op amps per node or one embedded processor chip per node for the more flexible implementations.
In one preferred embodiment of the present invention, a distributed market based analog control system includes multiple producing units, each producing unit having an output responsive to a market price. Production levels are in part determined by needs of multiple consuming units, each consuming unit also having an input responsive to a market price. Communication of pricing information between the producing units and the consuming units is mediated by a marketwire connecting multiple producing units to multiple consuming units. Absolute or relative voltage level, current level, or frequency of voltage or current level changes can all be used to represent price information on the marketwire. For voltage level based pricing schemes, typically voltages of about 5-10 volts are used. Since n
Berlin Andrew A.
Biegelsen David K.
Hogg Tad H.
Jackson Warren B.
LandOfFree
Distribution of partitionable physical properties for market... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distribution of partitionable physical properties for market..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distribution of partitionable physical properties for market... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3043707