Contract Net Protocol
Contract Net Protocol (CNP) is a well known task sharing protocol that is used for task allocation in multi-agent systems and consists of a collection of nodes or software agents that form the contract net. Each node on the network can, at different times or for different tasks be a manager or a contractor.
When a node gets a composite task (or for any reason cannot solve the present task) it breaks the problem down into sub-tasks (If possible) and announces the sub-task to the contract net acting as a manager. Bids are then received from potential contractors which the winning contractor(s) are awarded the job(s).
The Contract Net
Task distribution is viewed as a kind of contract negotiation and happens in 5 stages.
- Recognition
- Announcement
- Bidding
- Awarding
- Expediting
Recognition
An agent recognises it has a problem that it wants help with. The agent has a goal, and either:
- Realises it cannot achieve the goal in isolation - does not have the capability to fulfil the goal
- Realises it would prefer not to achieve the goal in isolation - typically because of solution quality, deadline, etc.
Announcement
The agent with the task sends out an announcement of the task which includes a specification of the task to be achieved. The specification must encode:
- Description of the task itself
- Any constraints
- Meta-task information
Bidding
Agents that receive the announcement decide themselves whether they should bid for the task. Factors that are taken into consideration are:
- The agent must decide whether it is capable of the expecting task
- The agent must determine the quality constrains and the price information (if relevant)
Awarding
Agents that send the task announcement must choose between the received bids and decide who to award the contract to. The result of this process is communicated to agents that submitted a bid.
Expediting
The successful contractor then expedites the task. This may involve the generation of further contract nets in the form of sub-contracting to complete the task.
Example uses of Contract Net Protocol
An electronic market place for buying and selling goods. For example a system where a user could specify the goods that they want as well as a maximum price that they are willing to pay. The agent programs then would find other user(s) willing to sell the goods within the desired price range. The user with the lowest price would then be selected to fulfill the contract. Other constraints could be applied such as delivery time and the location of the goods.[1]
References
See also