文章基本信息

标题：Dynamic CSP with Decision Transition Costs and its Solutions
本地全文：下载
作者：Daisuke Hatano ; Katsutoshi Hirayama
期刊名称：人工知能学会論文誌
印刷版ISSN：1346-0714
电子版ISSN：1346-8030
出版年度：2013
卷号：28
期号：1
页码：34-42
DOI：10.1527/tjsai.28.34
出版社：The Japanese Society for Artificial Intelligence
摘要：The dynamic constraint satisfaction problem (DynCSP) is a sequence of CSP instances. By introducing a notion of decision transition costs , one natural optimization problem results, where we search for a sequence of solutions that minimizes a total sum of decision transition costs. We will refer to this problem as the dynamic constraint satisfaction problem with decision transition costs (DynCSP-DTC). Previously, Hatano and Hirayama have presented an integer linear programming formulation to apply Lagrangian decomposition to the SAT-version of the problem called Dynamic SAT with decision change costs(DynSAT-DCC). However, since their linear encoding of decision change costs was specially designed for DynSAT, a new encoding method is required when we try to extend Lagrangian decomposition to solve general DynCSP-DTC. In this paper, we will introduce the quadratic encoding of decision transition costs that enables Lagrangian decomposition to work on general DynCSP-DTC including DynSAT-DCC. Furthermore, we empirically show that, even on DynSAT-DCC, Lagrangian decomposition with quadratic encoding performs more efficiently than other methods.
关键词：CSP ; Dynamic CSP ; Weighted CSP ; Lagrangian decomposition ; planning