کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9650046 | 658412 | 2005 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Adopt: asynchronous distributed constraint optimization with quality guarantees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Adopt: asynchronous distributed constraint optimization with quality guarantees Adopt: asynchronous distributed constraint optimization with quality guarantees](/preview/png/9650046.png)
چکیده انگلیسی
The Distributed Constraint Optimization Problem (DCOP) is a promising approach for modeling distributed reasoning tasks that arise in multiagent systems. Unfortunately, existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while allowing agents to operate asynchronously. We show how this failure can be remedied by allowing agents to make local decisions based on conservative cost estimates rather than relying on global certainty as previous approaches have done. This novel approach results in a polynomial-space algorithm for DCOP named Adopt that is guaranteed to find the globally optimal solution while allowing agents to execute asynchronously and in parallel. Detailed experimental results show that on benchmark problems Adopt obtains speedups of several orders of magnitude over other approaches. Adopt can also perform bounded-error approximation-it has the ability to quickly find approximate solutions and, unlike heuristic search methods, still maintain a theoretical guarantee on solution quality.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 161, Issues 1â2, January 2005, Pages 149-180
Journal: Artificial Intelligence - Volume 161, Issues 1â2, January 2005, Pages 149-180
نویسندگان
Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, Makoto Yokoo,