Data processing: generic control systems or specific application – Generic control system – apparatus or process – Plural processors
Reexamination Certificate
2000-07-28
2003-11-11
Gordon, Paul P. (Department: 2121)
Data processing: generic control systems or specific application
Generic control system, apparatus or process
Plural processors
C700S100000
Reexamination Certificate
active
06647300
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
BACKGROUND OF THE INVENTION
The present invention relates to industrial control systems and the like and in particular to an industrial control system comprised of many distributed controllers dividing job tasks among themselves using “market model” based bids and counter bids.
In a centralized model for industrial control, a single central controller (being a specialized computer) coordinates all aspects of the controlled process. Input signals representing values from sensors on the controlled process are communicated to the central controller which executes a control program to develop output signals which are communicated to actuators on the controlled process.
The centralized model is conceptually simple and requires programming only a single device. Nevertheless, the centralized model has some disadvantages. Control systems using this model are particularly vulnerable to failure of the single central controller. Further, communication of all I/O signals to a central location and executing the control program on a single computer, particularly for large control systems, can place undue burdens on processing resources and communication bandwidth.
In the distributed model for industrial control, the control program is executed by a number of spatially separate controllers intercommunicating only as needed on a common network. By placing these controllers near relevant I/O points, the communication of large amounts of I/O data is diminished. Having multiple control devices can also reduce the susceptibility of the control system to failure of any one device.
One difficulty with distributed control is that of developing the multiple control programs to dividing the control tasks among the various distributed controllers and coordinating their actions. One promising method of both dividing the control task among the controllers and coordinating their actions borrows from a market model of the economy in which many different autonomous individuals organize themselves (through bidding and counter bidding) to produce complex products or services without central control. In such autonomous cooperative systems (ACS), a job description is presented to a large number of autonomous cooperative units (ACUs), which, based on knowledge of their own capabilities and limitations, bid on portions of the job and counter bid in response to requests for bids. Control programs are simply developed and the potential exists for control programs to be quickly changed as new circumstances develop. Examples of this would be if it is desired to produce a new product or if ACUs (and associated equipment) are introduced or removed from the system. A description of some such of autonomous control systems are described in co-pending patents.
For an autonomous cooperative system to produce an optimized outcome, it is desirable that many different of divisions of the job among the ACUs be explored and thus that a large number of bids be collected from many different ACUs. This is done by allowing each ACU to make multiple simultaneous requests for bids from other ACUs. It follows that a single ACUs may receive multiple requests for bids from multiple other ACUs each of which must be considered in a separate “context” and each of which may mature into a different completed bid.
The bidding process for each context requires a large number of bidding messages be transmitted over the network
16
. Such messages generally include “bid requests” and replies to bid requests including “bid success”, “bid failure” and “counter bid” messages. The numbers of messages increases geometrically with the number of ACUs involved and these messages can easily overtax even high-speed communication networks thus delaying the determination of a control solution. This delay limits the usefulness of an ACS in responding quickly to changing control situations and effectively limits the size of control problems that may be advantageously handled by the ACS.
What is needed is a way to realize a freely scalable ACS system that may rapidly determine an optimized control solution that may be implemented with existing hardware having network bandwidth and processing limitations.
BRIEF SUMMARY OF THE INVENTION
The present invention allows complex, multi-context bids combinations to be freely explored by an ACS while still obtaining bid closure within an acceptable time. This is done by attaching a bid response time to each top-level bid. As sub-bids are propagated, they take this bid response time and subtract an amount related to their processing time, and forward that to other bidding partners. Bidding stops when the bid response time (as successively modified) is insufficient for further sub-bids.
As an adjunct to the goal of allowing bid solution space to be freely explored, the present invention also significantly reduces the number of bid messages needed to provide a solution, and thus requires less network bandwidth and ACU processing power. This is done by reporting to each ACU that was part of a successful bid together with the information about the sub-bidding partner of that ACU. In future bidding situations, the given ACU preferentially bids with those sub-bidding partners that were earlier part of a successful bid.
Specifically then, the present invention provides an apparatus for and method of coordinating a plurality of autonomous control units (ACUs) to control associated equipment. In a first step, a given ACU receives from a prior ACU a description of at least a portion of a job to be bid upon, together with a given bid response time limit after which a bid will not be accepted by the prior ACU. When a primary part of the job portion matches the capabilities of the given ACU, that ACU communicates a secondary part of the job portion not matching the capabilities of the given ACU over a network to at least one subsequent ACU together with a subsequent bid response time less than the given bid response time limit after which a bid will not be accepted by the given ACU. These steps are repeated with the subsequent ACU acting as the given ACU and a new ACU acting as the subsequent ACU.
Thus it is one object of the invention provide a predictable time limit to the bidding process that is compatible with the decentralized nature of the bidding system. The time limit of the bid response time may be passed along with each bid request to close all bids without the intervention of a central controller.
The subsequent bid response time may equal the given bid response time minus the time required by the given ACU to process the second part of the job for further communication over the network.
Thus it is another object of the invention to allow the sub-bidding process to continue to the last possible moment after which sub-bids could not be collected into a completed bid.
When a primary part of the job portion does not match the capabilities of the given ACU, the secondary part is not communicated to the subsequent ACU and a bid failure message is communicated to the prior ACU.
Thus it is another object of the invention to terminate bid message traffic on all chains that will be unsuccessful even if the time limit has not been exceeded.
The given ACU may receive, from at least one prior ACU a first and second description of at least a first and second different job portion with associated first and second given bid response times after which bids will not be accepted by the prior ACU. In this case, the given ACU may identify a primary part of the first and second job portion each matching the capabilities of the given ACU and a secondary part of the first and second job portions not matching the capability of the ACU. The given ACU may then communicate a description of the first and second secondary part of the first and second job portions over the network to at least two subsequent ACUs together with a third and fourth subsequent bid response time limit less than the given first and second bid response times, respectively.
T
Balasubramanian Sivaram
Maturana Francisco P.
Gain, Jr. Edward F.
Gerasimow Alexander M.
Gordon Paul P.
Quarles & Brady LLP
Rockwell Automation Technologies Inc.
LandOfFree
Bidding partner cache for autonomous cooperative control system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bidding partner cache for autonomous cooperative control system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bidding partner cache for autonomous cooperative control system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3160055