계약망 프로토콜

Contract Net Protocol

CNP(Contract Net Protocol)는 다중 에이전트 시스템의 태스크 공유 프로토콜로, 1980년 Reid G.[1] Smith에 의해 도입되었습니다.Autonomous 에이전트 간에 작업을 할당하는 데 사용됩니다.그것은 밀봉된 경매 프로토콜에 가깝다.주로 하청업체에 의존합니다.매니저는 여러 에이전트에게 작업을 제안합니다.후자는 관리자가 작업을 할당하도록 선택하는 제안을 합니다.그런 다음 이 작업을 분할하고 하청할 수 있습니다.

형식 설명

프로토콜의 공식화는 음성 행위 이론을 통해 수행될 수 있다.이 프로토콜에서 각 에이전트는 관리자 또는 계약자가 될 수 있습니다.

  1. 관리자가 제안 콜을 계약자에게 보내는 프로토콜 초기화
  2. 청부업자는 관심이 있는 경우 제안서를 보내거나 관심이 없는 경우 거절할 수 있습니다.이 제안서에는 관리자가 선택을 위해 필요한 모든 요소가 포함되어 있습니다.
  3. 관리자는 제안서 중에서 가장 적합한 제안서를 선택하여 해당 계약자에게 승낙서를 보냅니다.그것은 다른 계약자들에게 거절을 보내 그들의 결정을 알립니다.
  4. 계약이 성사되면 계약자는 통보 메시지를 사용하여 관리자에게 알립니다.전달해야 할 결과가 있는 경우, 인폼메시지를 통해서도 전달됩니다.계약자가 계약을 이행할 수 없는 경우에는 취소 메시지를 통해 관리자에게 알립니다.

Contract Net Protocol은 AUML 형식주의를 사용하여 나타낼 수 있습니다.

Contract Net Protocol AUML Diagram

이 프로토콜을 사용하여 계층적 조직을 구현할 수 있습니다. 여기서 관리자는 계약자에게 태스크를 할당하고 계약자는 하위 레벨의 태스크로 분해하여 하위 레벨에 할당합니다.이러한 종류의 조직은 에이전트가 협조적일 때(즉, 목적이 같을 때) 사용할 수 있습니다.이 경우 계약자가 제안할 때 관리자에게 거짓말을 하지 않도록 할 수 있다.에이전트가 경쟁력을 갖추면 프로토콜은 경매와 [2]매우 유사한 시장 조직에 귀속됩니다.

실행

이 프로토콜은 FIPA에 의해 ACL(에이전트 통신 언어)[3]로 구현되었습니다.

Contract Net Protocol은 다양한 문제와 상황에 대해 구현되어 있습니다.원본 문서에서는 센서 네트워크의 사용 사례에 대해 설명합니다.후속 연구는 이 [4]맥락에서 그 효용을 보여주었다.또한 다중 로봇 작업 [5]할당에도 사용되었습니다.또한 e커머스 마켓플레이스와 [7]공급망 모두에서 협상 프로토콜로 사용되어 왔습니다.

문제 및 확장

Reid G Smith는 그 프로토콜과 관련된 몇 가지 문제를 확인했다.특히, 그는 교환된 메시지의 관점에서 네트워크 통신에 과부하가 걸리는 것을 피하기 위해 짧은 메시지만 만들고 제안된 태스크와 관련될 수 있는 에이전트와만 대화할 것을 제안합니다.관리자가 어떤 계약자와 계약하고 싶은지 알고 있는 경우에는 계약자가 받아들일 수 있는지 여부에 관계없이 직접 연락하여 제안을 할 수 있다.

두 번째 문제는 업무가 많을 때 도급업자의 점유율과 관련이 있다.실제로, 이 경우, 관리자는 이용 가능한 계약자를 찾는 것이 복잡할 수 있습니다.이 문제를 해결하기 위해 계약자는 이미 다른 계약을 체결하고 있는 경우에도 제안서에 응답할 수 있습니다.이 수법은 계약자가 모두 바쁘기 때문에 매니저가 아무런 답변도 없이 제안을 하는 상황을 막기 위해 사용할 수 있습니다.이 경우 청부업자는 매니저의 제안서에 서명할 준비가 되는 순간을 제안서에 추가합니다.마찬가지로 관리자가 먼저 연락할 수 있도록 사용 가능한 모든 계약업체 목록을 보관할 수 있습니다.이 트릭을 사용하면 매니저가 제안서를 모든 에이전트에 여러 번 송신하기 때문에 네트워크의 과부하를 회피할 수 있습니다.또, 최종적으로 제안된 작업을 계약하는 계약업자를 찾을 수 있습니다.이 정보는 계약자가 관리자에게 직접 보냅니다.

저자가 제안한 확장 기능 외에도 여러 저작물이 계약망 프로토콜을 확장했습니다.이로 인해 제기된 문제점 중 하나는 매니저가 가장 가치 있는 것을 정확하게 파악할 수 없다는 사실이다.청부업자로부터 받은 제안 중에서 선택해야 합니다.각 계약자가 다양한 제안을 할 수 있는 경우, 이는 차선의 해결책으로 이어질 수 있습니다.이 문제를 해결하기 위해 FIPA는 또한 관리자가 이에 응답한 계약자 중 일부는 제안하고 다른 일부는 거부하여 최종적으로 그들 중 하나를 받아들일 수 있는 반복된 버전의 프로토콜을 제안합니다.결과 프로토콜은 반복된 경매 프로토콜과 비교할 수 있습니다.CNP로서 이 프로토콜은 AUML 다이어그램으로 나타낼 수 있습니다.

Iterated Contract Net Protocol AUML diagram

프로토콜의 또 다른 문제는 실제로 작업을 처리하는 것입니다.원래 프로토콜에서, 제안을 하는 계약자는 어떠한 대가를 치르더라도 자신이 제안한 작업을 수행하도록 커밋합니다.업무의 실패는 계약자의 어떠한 승인도 받지 않고, 업무는 처리되지 않는다는 것을 관리자에게 알리는 취소 메시지를 통해서만 고려됩니다.대리인이 이기적인 경우, 그들은 가능한 한 많은 제안을 하고 가장 수익성이 높은 제안만 이행하도록 동기를 부여할 수 있다.콜라보레이션 컨텍스트에서 에이전트는 다른 태스크에 커밋하기 위해 태스크에서 제외하는 것이 시스템 전체에 적합한지 여부를 알 수 없습니다.Tuomas Sandholm과 Victor Lesser는 1995년에 이러한 요소들을 고려하여 계약자가 [9]임무를 수행할 수 없을 때 지불해야 하는 약정 비용을 미리 정의하기 위해 프로토콜의 확장을 발표했다.

레퍼런스

  1. ^ Smith (December 1980). "The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver". IEEE Transactions on Computers. C-29 (12): 1104–1113. doi:10.1109/TC.1980.1675516. ISSN 0018-9340. S2CID 15267324.
  2. ^ Horling, Bryan; Lesser, Victor (2005-11-11). "A survey of multi-agent organizational paradigms". The Knowledge Engineering Review. 19 (4): 281. doi:10.1017/S0269888905000317. ISSN 0269-8889. S2CID 562855.
  3. ^ "FIPA Contract Net Interaction Protocol Specification". fipa.org. Retrieved 2019-04-09.
  4. ^ Chen, L.; Xue-song, Q.; Yang, Y.; Gao, Z.; Qu, Z. (July 2012). "The contract net based task allocation algorithm for wireless sensor network". 2012 IEEE Symposium on Computers and Communications (ISCC). pp. 000600–000604. doi:10.1109/ISCC.2012.6249362. ISBN 978-1-4673-2713-8. S2CID 11799626.
  5. ^ Grabovskis, Arvids; Lavendelis, Egons; Liekna, Aleksis (2012-11-08). "Experimental analysis of contract net protocol in multi-robot task allocation". Applied Computer Systems. 13 (1): 6–14. doi:10.2478/v10312-012-0001-7.
  6. ^ Sandholm, Tuomas (1993). "An implementation of the contract net protocol based on marginal cost calculations" (PDF). AAAI-93 Proceedings. pp. 256–262.
  7. ^ (Roger) Jiao, Jianxin; You, Xiao; Kumar, Arun (July 2006). "An agent-based framework for collaborative negotiation in the global manufacturing supply chain network". Robotics and Computer-Integrated Manufacturing. 22 (3): 239–255. doi:10.1016/j.rcim.2005.04.003.
  8. ^ "FIPA Iterated Contract Net Interaction Protocol Specification". fipa.org. Retrieved 2019-04-09.
  9. ^ Sandholm, Tuomas; Lesser, Victor (1995). "Issues in automated negotiation and electronic commerce: Extending the contract net framework" (PDF). Proceedings of the First International Conference on Multiagent Systems. pp. 328–335.

「 」를 참조해 주세요.