In scenarios with numerous emergencies that arise and require the assistance of various rescue units (e.g., medical, fire, \& police forces), the rescue units would ideally be allocated quickly and distributedly while aiming to minimize casualties. This is one of many examples of distributed settings with service providers (the rescue units) and service requesters (the emergencies) which we term \textit{service oriented settings}. Allocating the service providers in a distributed manner while aiming for a global optimum is hard to model, let alone achieve, using the existing Distributed Constraint Optimization Problem (DCOP) framework. Hence, the need for a novel approach and corresponding algorithms. We present the Service Oriented Multi-Agent Optimization Problem (SOMAOP), a new framework that overcomes the shortcomings of DCOP in service oriented settings. We evaluate the framework using various algorithms based on auctions and matching algorithms (e.g., Gale Shapely). We empirically show that algorithms based on repeated auctions converge to a high quality solution very fast, while repeated matching problems converge slower, but produce higher quality solutions. We demonstrate the advantages of our approach over standard incomplete DCOP algorithms and a greedy centralized algorithm.
翻译:在出现并需要各种救援单位(如医疗、消防、警力等)协助的众多紧急情况下,最好能够迅速分配救援单位,并分配救援单位,同时尽量减少伤亡,这是服务提供方(救援单位)和服务请求方(紧急情况)分布式环境的许多例子之一,我们称之为“救助单位”和服务请求方(紧急情况)。用分布式方式分配服务提供方,同时力求实现全球最佳化,很难建模,更不用说利用现有的分散式优化问题(DCOP)框架实现。因此,需要采用新颖的方法和相应的算法。我们介绍了面向服务的多点优化问题(SOMAOP),这是一个克服DCOP在以服务为导向的环境中缺陷的新框架。我们利用基于拍卖和匹配算法(例如Gale Shapely)的各种算法评估框架。我们从经验上表明,基于反复拍卖的算法会快速地达到高质量解决方案,同时重复的匹配问题趋近,但产生更高的质量解决方案。我们展示了一种不完全可靠的D级算法的优势。</s>