Print Email Facebook Twitter Inefficiencies in Task Allocation for Multiagent Planning with Bilateral Deals Title Inefficiencies in Task Allocation for Multiagent Planning with Bilateral Deals Author De Weerdt, M.M. Van der Krogt, R.P.J. Faculty Electrical Engineering, Mathematics and Computer Science Department Software Computer Technology Date 2006-12-14 Abstract Distributed planning in a multiagent environment may give rise to inefficiencies. We study this effect focussing on the task allocation problem. We show that in the worst case, the result of a multiagent approach can be arbitrarily bad in theory when recontracting and multilateral deals are not allowed. This is a more precise result than was previously known, which was that we are not guaranteed to find the optimal solution. We show that the sources of this disappointing result are the impossibility to come back on (bad) contracts in combination with either selfish agents, or agents that have incomplete information on potential costs. Furthermore, we show some preliminary experimental results of the effect of these causes on the optimality of a solution for multiagent task allocation. Interestingly, none of the experiments exhibit the very negative outcomes that are predicted by the theory. Although it is too early to draw conclusions, this might indicate that in practical situations, the circumstances that lead to the theoretical results are very unlikely. To reference this document use: http://resolver.tudelft.nl/uuid:9b3672ac-2b99-4eae-9e4c-d2cfec9e43c1 Publisher University of Nottingham Source PlanSIG 2006: Proceedings of the 25th Workshop of the UK Planning and Scheduling Special Interest Group, Nottingham, UK, 14-15 December 2006 Part of collection Institutional Repository Document type conference paper Rights (c) 2006 The Author(s) Files PDF plansig06weerdt1.pdf 121.32 KB Close viewer /islandora/object/uuid:9b3672ac-2b99-4eae-9e4c-d2cfec9e43c1/datastream/OBJ/view