Bidding partner cache for autonomous cooperative control system

• US 6,647,300 B1
• Filed: 07/28/2000
• Issued: 11/11/2003
• Est. Priority Date: 07/28/2000
• Status: Expired due to Fees

• Current Assignee: Rockwell Technologies, LLC
• Original Assignee: Rockwell Automation Technologies Incorporated (Allen-Bradley Co., Inc.)
• Inventors: Maturana, Francisco P., Balasubramanian, Sivaram
• Primary Examiner(s): Gordon, Paul P.
• Assistant Examiner(s): GAIN, EDWARD F
• Application Number:
  US09/627,984
• Time in Patent Office: 1,201 Days
• Field of Search: 700/4, 700/3, 700/2, 700/9, 700/20, 700/99, 700/103, 700/97, 700/100
• US Class Current: 700/4
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: Y02P 80/40 Minimising material used in manufacturing processes
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

A distributed control system employs a number of autonomous cooperative units that intercommunicate with bids and counter bids to allocate the production of a product among them. Bidding closure is obtained in an environment where each autonomous cooperative unit can propagate multi-threaded bidding chains, by attaching a response time value to each propagated bid indicating when a response must be received. Sub-bids from that propagated bid forward a reduced version of this response time value that accounts for the sub-bid processing time. Thus, all bidding is concluded within the response time value. Participants in a successful bidding chain are notified so that in the future they may direct bids toward bidding partners that have historically proven successful as part of a successful bidding chain.

Claims

1. A method of coordinating a plurality of autonomous control units (ACUs) to control associated equipment, the ACUs implemented in computers and having capabilities describing operations performable by the equipment associated with the ACUs, the ACUs intercommunicating on an electronic network to divide a predefined job requiring the capabilities among ACUs by a bidding message communicated among ACUs on the electronic network, the method comprising the steps of:

(a) receiving at a given ACU from a prior ACU, a description of at least a portion of the job together with a given bid response time limit after which a bid will not be accepted by the prior ACU;

(b) when a primary part of the job portion matching the capabilities of the given ACU can be identified, communicating a secondary part of the job portion not matching the capabilities of the given ACU over the 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;

(c) repeating steps (a) and (b) with the subsequent ACU acting as the given ACU and a new ACU acting as the subsequent ACU;

whereby chains of bids are truncated at a limiting time.

2. The method of claim 1 wherein the subsequent bid response time equals 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.

3. The method of claim 1, wherein when a primary part of the job portion does not match the capabilities of the given ACU, including the step of not communicating of the secondary part to the subsequent ACU and communicating a bid failure message to the prior ACU.

4. The method of claim 1 wherein the given ACU receives 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;

and wherein

the given ACU identifies a primary part of the first and second job portions, 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; and

wherein

the given ACU communicates 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.

5. The method of claim 1 further including the step of:

subsequent to step (b), in response to the communicated secondary part of the job portion, receiving at the given ACU within the given bid response time, at least one reply bid message from a subsequent ACU, the reply bid message selected from the group consisting of;

(i) bid success messages, indicating that the secondary part of the job portion matches the capability of a subsequent ACU,

(ii) bid failure messages indicating that the secondary part of the job portion does not match the capability of a subsequent ACU and

(iii) a bid modification message indicating that the secondary part of the job portion might match the capability of a subsequent ACU with some modification of the secondary part of the job description,

and further including the steps of;

(1) when the reply includes at least one bid success message, forwarding to the prior ACU only the bid success messages;

(2) when the reply includes no bid success messages but at least one bid modification message, forwarding to the prior ACU only the bid modification messages;

(3) when the reply includes no bid success messages and no bid modification messages, but at least one bid failure message, forwarding to the prior ACU only the bid failure messages.

6. The method of claim 1 wherein

step (c) includes the step of reporting a bid success from the given ACU to the initial ACU for the primary part of the job;

and including further the steps of;

(d) identifying at an initial ACU successful ACUs being part of a sequence of ACU reporting bid successes for the complete job;

(e) communicating to each of the successful ACUs the identify of ACUs subsequent to the successful ACU in the sequence;

repeating steps (a)-(e) wherein at a subsequent step (b), the given ACU communicates preferentially with subsequent ACUs identified at an earlier step (e).

7. A method of coordinating a plurality of autonomous control units (ACUs) to control associated equipment, the ACUs implemented in computers and having capabilities describing operations performable by the equipment associated with the ACUs, the ACUs intercommunicating on an electronic network to divide a predefined job requiring the capabilities among ACUs by a bidding message communicated among ACUs on the electronic network, the method comprising the steps of:

(a) communicating from an initial ACU a bid request for a job to multiple given ACUs;

(b) at each given ACU, identifying a primary part of the job matching the capabilities of the given ACU and a secondary part of the job not matching the capability of the given ACU;

(c) reporting a bid success from the given ACU to the initial ACU for the primary part of the job;

(d) communicating from the given ACU to subsequent ACUs additional bid requests related to the secondary part of the job portion;

(e) repeating steps (a)-(c) with the subsequent ACU acting as the given ACU;

(f) identifying at the initial ACU successful ACUs being part of a sequence of ACU reporting bid successes for the complete job;

(e) communicating to each of the successful ACUs the identity of ACUs subsequent to the successful ACU in the sequence;

repeating steps (a)-(e) wherein at a subsequent step (d) the given ACU communicates preferentially with ACU identified at an earlier step (e).

8. The method of claim 7 wherein the successful ACUs assign priority value to other ACUs dependant upon the number of times the other ACU were identified in step (e) and applies a threshold value to the priority values to communicate in step (d) only with ACU whose priority values exceed the threshold value.

9. The method of claim 7 wherein the threshold value is changed for subsequent repetitions of steps (a) through (e) depending on the number of ACU whose priority values exceed the threshold value.

10. The method of claim 7 wherein step (c) of reporting a bid success from the given ACU to the initial ACU for the primary part of the job also passes along reports from subsequent ACU.

11. An industrial controller comprising:

(I) an electrical network for digital communication;

(II) a plurality of autonomous control units (ACUs) implemented in computers and intercommunicating on an electronic network to divide a predefined job among ACUs by a bidding message communicated among ACUs on the electronic network, the ACUs further being in electrical communication with associated equipment and having capabilities describing operations performable by the associated equipment, the ACUs executing a stored program to;

(a) receive at a given ACU from a prior ACU, a description of at least a portion of the job together with a given bid response time limit after which a bid will not be accepted by the prior ACU;

(b) when a primary part of the job portion matching the capabilities of the given ACU can be identified, communicate a secondary part of the job portion not matching the capabilities of the given ACU over the 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;

(c) repeat steps (a) and (b) with the subsequent ACU acting as the given ACU and a new ACU acting as the subsequent ACU;

whereby chains of bids are truncated at a limiting time.

12. The industrial controller of claim 11 wherein the ACUs further execute the stored program so that the subsequent bid response time equals 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.

13. The industrial controller of claim 11, wherein the ACUs further execute the stored program so as, when the primary part of the job portion does not match the capabilities of the given ACU, to including the program step of not communicating of the secondary part to the subsequent ACU and communicating a bid failure message to the prior ACU.

14. The industrial controller of claim 11 wherein the ACUs further execute the stored program so that the given ACU receives 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;

and wherein

the given ACU identifies a primary part of the first and second job portions 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; and

wherein

the given ACU communicates 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.

15. The industrial controller of claim 11 further including the program step of:

subsequent to step (b), in response to the communicated secondary part of the job portion, receiving at the given ACU within the given bid response time, at least one reply bid message from a subsequent ACU, the reply bid message selected from the group consisting of;

(i) bid success messages, indicating that the secondary part of the job portion matches the capability of a subsequent ACU,

(ii) bid failure messages indicating that the secondary part of the job portion does not match the capability of a subsequent ACU; and

(iii) a bid modification message indicating that the secondary part of the job portion might match the capability of a subsequent ACU with some modification of the secondary part of the job description,

and further including the steps of;

(1) when the reply includes at least one bid success message, forwarding to the prior ACU only the bid success messages;

(2) when the reply includes no bid success messages but at least one bid modification message, forwarding to the prior ACU only the bid modification messages;

(3) when the reply includes no bid success messages and no bid modification messages, but at least one bid failure message, forwarding to the prior ACU only the bid failure messages.

16. The industrial controller of claim 11 wherein the ACUs further execute the stored program so that:

program step (c) includes the step of reporting a bid success from the given ACU to the initial ACU for the primary part of the job;

and including further the program steps of;

(d) identifying at an initial ACU successful ACUs being part of a sequence of ACU reporting bid successes for the complete job;

(e) communicating to each of the successful ACUs the identity of ACUs subsequent to the successful ACU in the sequence;

repeating program steps (a)-(e) wherein at a subsequent program step (b) the given ACU communicates preferentially with subsequent ACUs identified at an earlier step (e).

17. An industrial controller comprising:

(I) an electrical network for digital communication;

(II) a plurality of autonomous control units (ACUs) implemented in computers and intercommunicating on an electronic network to divide a predefined job among ACUs by a bidding message communicated among ACUs on the electronic network, the ACUs further being in electrical communication with associated equipment and having capabilities describing operations performable by the associated equipment, the ACUs executing a stored program to;

(a) communicate from an initial ACU a bid request for a job to multiple given ACUs;

(b) at each given ACU, identify a primary part of the job matching the capabilities of the given ACU and a secondary part of the job not matching the capability of the given ACU;

(c) report a bid success from the given ACU to the initial ACU for the primary part of the job;

(d) communicate from the given ACU to subsequent ACUs additional bid requests related to the secondary part of the job portion;

(e) repeat steps (a)-(c) with the subsequent ACU acting as the given ACU;

(f) identify at the initial ACU successful ACUs being part of a sequence of ACU reporting bid successes for the complete job;

(e) communicate to each of the successful ACUs the identity of ACUs subsequent to the successful ACU in the sequence;

repeat steps (a)-(e) wherein at a subsequent step (d) the given ACU communicates preferentially with ACU identified at an earlier step (e).

18. The industrial controller of claim 17 wherein the ACUs further execute the stored program so that the successful ACUs assigns priority value to other ACUs dependant upon the number of times the other ACUs were identified in program step (e) and applies a threshold value to the priority values to communicate in program step (d) only with ACU whose priority values exceed the threshold value.

19. The industrial controller of claim 17 wherein the ACUs further execute the stored program so that the threshold value is changed for subsequent repetitions of program steps (a) through (e) depending on the number of ACU whose priority values exceed the threshold value.

20. The industrial controller of claim 17 wherein program step (c) of reporting a bid success from the given ACU to the initial ACU for the primary part of the job also passes along reports from subsequent ACU.