Contract Net Protocol

CNP formalizes a Manager-Contractor dynamic. A Manager agent decomposes a complex goal into sub-tasks and broadcasts an announcement. Contractor agents evaluate the task against their own capabilities and current commitments. This creates a clear, temporary hierarchy for each task instance, distinct from the system's overall architecture.

The protocol operates through a strict sequence of messages:

• Task Announcement: Manager broadcasts a task specification with eligibility criteria and a deadline.
• Bidding: Capable contractors submit bids detailing their cost, estimated duration, or quality level.
• Award: Manager evaluates all received bids and sends an exclusive award message to the winner.
• Expediting: The contractor confirms acceptance and later reports task completion or failure.

CNP supports two announcement strategies to balance overhead and relevance:

• General Broadcast: The task is announced to all agents. This maximizes the pool of potential bidders but increases communication overhead.
• Directed Announcement: The manager uses a knowledge base to identify a small subset of agents known to be capable, sending the announcement only to them. This reduces network load but risks missing a newly available agent.

An agent's decision to bid is not static. It is a real-time evaluation of eligibility and capacity. An agent must parse the task specification to determine if it possesses the required tool or skill. It then checks its current schedule to calculate if it can complete the work by the deadline without overloading its resources, often using a cost function to generate a competitive bid.

The protocol embeds a two-way evaluation. The manager evaluates bids based on a multi-attribute utility function (e.g., price, speed, quality). Simultaneously, a contractor can reject an award if its circumstances changed after bidding. This shared responsibility for commitment prevents the system from being locked into stale agreements and mirrors real-world subcontracting dynamics.

Classic CNP assumes cooperative agents and has no native security model, making it vulnerable to malicious bidders in open systems. It also lacks a mechanism for agents to share knowledge about the reputation of unreliable contractors. Extensions like Sandholm's leveled commitment protocols add penalties for contract decommitment to stabilize behavior in competitive settings.

A dynamic allocation method where production time slots or resources are assigned to the highest-bidding agent, optimizing for priority, due dates, or cost efficiency. This is the direct application of the Contract Net Protocol to manufacturing execution.

• Combinatorial Auctions: Allow agents to bid on bundles of contiguous time slots to minimize setup times.
• Vickrey Auctions: Incentivize truthful bidding by charging the second-highest price, preventing strategic manipulation.
• Reverse Auctions: A manager agent solicits bids for a task, and the lowest-cost capable agent wins the contract.

A standardized agent communication language defined by the Foundation for Intelligent Physical Agents that structures the semantics of messages exchanged between industrial agents. It provides the formal envelope for Contract Net negotiations.

• Defines performatives like CFP (Call for Proposals), PROPOSE, ACCEPT-PROPOSAL, and REJECT-PROPOSAL.
• Encodes the ontology and content language so heterogeneous agents share a common understanding.
• Enables interoperability between agents built on different platforms, crucial for multi-vendor factory floors.

The coordination framework that manages dependencies, communication, and resource allocation between heterogeneous autonomous agents to execute a shared manufacturing workflow. Contract Net is one specific negotiation protocol within this broader orchestration layer.

• Directed Acyclic Graph (DAG) Execution: Defines task dependencies to prevent circular waits.
• Saga Pattern: Manages long-running transactions with compensating actions if a sub-task fails.
• Deadlock Detection: Monitors for circular wait states where agents block each other indefinitely.

The field of designing auction rules and incentive structures so that self-interested agents are motivated to reveal truthful information, resulting in globally optimal supply chain outcomes. It addresses the strategy-proofness of protocols like Contract Net.

• VCG Auction: A sealed-bid combinatorial mechanism where winning agents pay the marginal harm their win imposes on others.
• Incentive Compatibility: Ensures an agent's dominant strategy is to bid its true cost and capability.
• Prevents gaming where agents artificially inflate urgency to capture premium time slots.

A coordination mechanism where agents communicate indirectly by modifying a shared environment, such as a digital production schedule or a Blackboard Architecture. This contrasts with the direct negotiation of Contract Net.

• Agents deposit partial solutions or status updates on a shared data structure.
• Other agents sense these environmental changes and adapt their behavior without point-to-point messages.
• Highly robust for swarm robotics and decentralized routing where direct communication is unreliable.

A mathematical framework where production scheduling is defined by variables, domains, and constraints, requiring an agent to find a valid assignment that satisfies all rules. Contract Net can be used to distribute CSP solving across agents.

• Variables: Tasks, machines, time slots.
• Domains: Capable machines, available time windows.
• Constraints: Precedence, capacity, due dates.
• Agents bid on variable assignments, and a manager ensures global constraint consistency.