Çok Etmenli Ortamlar İçin CNP Tabanlı Müzakere Protokolü

Abstract

Çok etmenli sistemlerde, etmenler arası görev dağıtımı önemli bir araştırma konusudur. Etmenler arası müzakereler için protokoller geliştirilmiştir. Bu protokoller arasında yer alan ve oldukça yaygın olan CNP, Smith ve Davis tarafından geliştirilmiştir. Bu protokol, ihale kavramına dayanan bir dağıtık görev atama müzakere modelidir. Yönetici ve adaylar vardır. Bu sistem dinamiktir ve herhangi bir anda yönetici ve adaylar katılabilir ya da ayrılabilirler. Ancak CNP protokolünün bazı kısıtları vardır. Görüşmeler sıralı olarak yapılır. Müzakereleri sırasallaştırmak bazı anlaşmaları kaçırmaya neden olabilir. Adaylar tarafından verilen teklifler, daha iyi fırsatların oluşması durumunda tutulmayabilir. Etmenlerin çökmesi durumunda ihale kilitlenebilir. Bu çalışmada çok etmenli bir ortamda taşımacılık problemi simüle edilmiş ve S.Aknine, S. Pinson, M.Shakun tarafından geliştirilmiş CNP protokolü gerçeklenerek yürütme ortamı sağlanmıştır. Çok etmenli ortamın yaratılması için JADE platformu kullanılmıştır. Yönetici ve aday sayıları değiştirilerek çeşitli deneyler yapılmış ve sonuçları kıyaslanmıştır. Başarı kriteri olarak sonuca ulaşmak için atlatılan adım sayısı ve müzakere sırasında geçen süre baz alınmıştır. Görev ve aday etmen sayısındaki artış ihale süresinin uzamasına neden olmaktadır. Ancak en iyi teklif bilgisinin iletildiği durumlarda, iletilmediği durumlara göre özellikle toplam etmen sayısının arttığı karmaşık sistemler için ihalelerin daha kısa sürede sonuçlandığı görülmüştür.

Multi-agent negotiation and task allocation is a fundamental research issue. Various negotiation protocols have been developed. One of them is the well known CNP protocol which is defined by Smith and Davis. It is used for decentralized task allocation and based on the notion of call for bids. There are manager and contractor agents. The system is dynamic and each agent on the network can join or leave the system at different times. The CNP protocol has some limitations. Firstly, in a distributed environment, several managers can concurrently call for bids, so an agent may have to manage several negotiation processes in parallel in order to reduce the length of its negotiation processes. Some applications of the CNP force the contractors to sequence their negotiation processes. Thus, when there are several managers that call for bids, contractors cannot give proposals in parallel. Thus negotiation processes take longer, and meanwhile, contractors may miss some contracts. Secondly, CNP-based applications enable the agent to break its commitments when an agent receives an offer for a better task in comparison with those for which the agent is committed. If a manager comes with a better task, contractors may break their commitments. This is not a good solution because it makes managers call again for bids to find new contractors for their tasks. In case of agent failures, negotiation processes may be blocked. This study describes the design and implementation of an agent based execution environment where agents follow the extended CNP negotiation protocol defined by S.Aknine, S. Pinson, M.Shakun during negotiations. An application based on a transportation problem has been developed to assess the system. In this study, JADE is used to implement the multi-agent system. Various experimental studies have been performed for different numbers of manager and contractor agents and the results are compared. The success key is the negotiation time and the number of the steps applied until the negotiation process is completed. Increased in the number of the contractor and manager agents cause the negotiation time take longer. Better results have been observed when the best offer is also sent by the PreReject message compared to not being sent, especially for more complex and crowded agent systems.