智能规划中面向简单偏好的高效求解方法
作者:
作者简介:

陆旭(1985-),男,博士,副教授,CCF专业会员,主要研究领域为智能规划,模型检测,程序验证;王德奎(1991-),男,博士,讲师,CCF专业会员,主要研究领域为FPGAEDA算法优化,脑电信号处理;于斌(1990-),男,博士,讲师,CCF专业会员,主要研究领域为模型检测,运行时验证;陈矗(1978-),男,博士,讲师,CCF专业会员,主要研究领域为软件安全检测,学习安全与隐私保护;段振华(1948-),男,博士,教授,博士生导师,CCF会士,主要研究领域为时序逻辑,形式化方法,高可信嵌入式系统;崔进(1989-),女,博士,讲师,CCF专业会员,主要研究领域为可信软件,实时系统,大数据计算.

通讯作者:

于斌,E-mail:byu@xidian.edu.cn;段振华 E-mail:zhhduan@mail.xidian.edu.cn

基金项目:

国家自然科学基金(61806158,61732013,62172322,62002290);中国博士后科学基金(2019T120881,2018M643585);国家重点研发计划(2018AAA0103202);陕西省重点科技创新团队项目(2019TD-001);陕西省自然科学基础研究计划(2021JQ-208);山东省自然科学基金(ZR2020MF030,ZR2018PF007);赛尔网络下一代互联网技术创新项目(NGII20190407);陕西省教育厅专项科研计划(21JK0844)


Efficient Approach for Solving Simple Preference in AI Planning
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [34]
  • |
  • 相似文献
  • | | |
  • 文章评论
    摘要:

    智能规划(AI planning)简称规划,是人工智能领域的一个重要分支,在各领域均有广泛应用,如工厂车间作业调度、物资运输调度、机器人动作规划以及航空航天任务规划等.传统智能规划要求规划解(动作序列)必须最终实现整个目标集合,这种目标一般被称为硬目标(hard goal).然而,许多实际问题中,求解的重点并不只是尽快实现目标以及尽量减少动作序列产生的代价,还需考虑其他因素,如资源消耗或时间约束等.为此,简单偏好(也称软目标soft goal)的概念应运而生.与硬目标相反,简单偏好是可以违背的.本质上,简单偏好用于衡量规划解质量的优劣,而不会影响规划解是否存在.现有关于简单偏好的研究进展缓慢,在规划解质量方面不尽如人意,即求得的规划解与最优解的差距较大.提出了一种求解简单偏好的高效规划方法,将简单偏好表达为经典规划(classical planning)模型的一部分,并利用SMT (satisfiability modulo theories)求解器识别多个简单偏好之间的各种关系,从而约简简单偏好集,减轻规划器的求解负担.该方法的主要优势在于:一方面,提前对简单偏好集进行裁剪,在一定程度上缩减搜索的状态空间;另一方面,直接利用现有高效经典规划器进行求解,而无须提出专用的规划算法,可扩展性较强.基准规划问题的实验结果表明,该方法在提升规划解质量方面表现优异,尤其适用于简单偏好之间不是相互独立的情况.

    Abstract:

    AI planning, or planning for short, is an important branch of AI and widely applied in many fields, e.g., job shop scheduling, transportation scheduling, robot motion planning, aerospace mission planning, etc. A plan (a sequence of actions) must achieve all goals eventually in traditional planning, where such goals are called hard goals. Nevertheless, in many practical problems, the key focus is not only on the realization of goals as soon as possible and the reduction of the cost of plans as low as possible, but also on other factors, e.g., resource consumption or time constraint. To this end, the concept of simple preference which is also called soft goals is introduced. In contrast to hard goals, a simple preference is allowed to be violated by a plan. In essence, simple preferences are used to measure the quality of plans, without affecting the existence of plans. Current research on simple preferences makes less progress and the quality of plans are often unsatisfactory. This study proposes an efficient approach for solving simple preferences which are modeled as a part of classical planning models. Moreover, SMT (satisfiability modulo theories) solver is employed to recognize the mutual exclusion relations among simple preferences for the purpose of preference reduction, relieving the burden of planers. The major advantages of this approach lie in: on one hand, the state space is largely reduced due to the pre-tailoring of simple preferences, and on the other hand, the existing fast planners can be utilized and there is no need to design specialized planning algorithm. The experimental results on benchmarks show that the proposed approach has sound performance in improving the quality of plans, especially suited for the situation where simple preferences are not independent of each other.

    参考文献
    [1] Malik G, Dana SN, Paolo T.Automated Planning-Theory and Practice.Elsevier, 2004.
    [2] Gerevini A, Long D.Preferences and soft constraints in PDDL3.In:Proc.of the ICAPS Workshop on Planning with Preferences and Soft Constraints.2006.46-53.
    [3] Baier JA, McIlraith SA.Planning with preferences.AI Magazine, 2008, 29(4):25-36.[doi:10.1609/aimag.v29i4.2204]
    [4] Son TC, Pontelli E.Planning with preferences using logic programming.Theory and Practice of Logic Programming, 2006, 6(5):559-607.[doi:10.1017/S1471068406002717]
    [5] Baier JA, Bacchus F, McIlraith SA.A heuristic search approach to planning with temporally extended preferences.In:Veloso MM, ed.Proc.of the 20th Int'l Joint Conf.on Artificial Intelligence (IJCAI 2007).2007.1808-1815.
    [6] Sohrabi S, Baier JA, McIlraith SA.HTN planning with preferences.In:Boutilier C, ed.Proc.of the 21st Int'l Joint Conf.on Artificial Intelligence (IJCAI 2009).2009.1790-1797.
    [7] Wright B, Mattmüller R, Nebel B.Compiling away soft trajectory constraints in planning.In:Thielscher M, Toni F, Wolter F, eds.Proc.of the 16th Int'l Conf.(KR 2018).2018.474-483.
    [8] Percassi F, Gerevini AE.On compiling away PDDL3 soft trajectory constraints without using automata.In:Benton J, Lipovetzky N, Onaindia E, et al., eds.Proc.of the 29th Int'l Conf.on Automated Planning and Scheduling (ICAPS 2019).2019.320-328.
    [9] Bonassi L, Gerevini AE, Percassi F, et al.On planning with qualitative state-trajectory constraints in PDDL3 by compiling them away.In:Biundo S, Do M, Goldman R, et al., eds.Proc.of the 31st Int'l Conf.on Automated Planning and Scheduling (ICAPS 2021).2021.46-50.
    [10] Mattmüller R, Geißer F, Wright B, et al.On the relationship between state-dependent action costs and conditional effects in planning.In:McIlraith SA, Weinberger KQ, eds.Proc.of the 32nd AAAI Conf.on Artificial Intelligence (AAAI 2018).2018.6237-6245.
    [11] Bofill M, Espasa J, Villaret M.Relaxed exists-step plans in planning as SMT.In:Sierra C, ed.Proc.of the 26th Int'l Joint Conf.on Artificial Intelligence (IJCAI 2017).2017.563-570.[doi:10.24963/ijcai.2017/79]
    [12] Bit-Monnot A, Leofante F, Pulina L, et al.SMT-based planning for robots in smart factories.In:Wotawa F, Friedrich G, Pill I, et al., eds.Proc.of the 32nd Int'l Conf.on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2019).2019.674-686.[doi:10.1007/978-3-030-22999-3\_58]
    [13] Sebastiani R, Tomasi R.Optimization in SMT with LA(Q) cost functions.In:Gramlich B, Miller D, Sattler U, eds.Proc.of the 6th Int'l Joint Conf.on Automated Reasoning (IJCAR 2012).2012.484-498.[doi:10.1007/978-3-642-31365-3\_38]
    [14] Chen L, Wang YJ, Wu JZ, et al.Rate-monotonic optimal design based on tree-like linear programming search.Ruan Jian Xue Bao/Journal of Software, 2015, 26(12):3223-3241(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4853.htm[doi:10.13328/j.cnki.jos.004853]
    [15] Blackham B, Liffiton MH, Heiser G.Trickle:Automated infeasible path detection using all minimal unsatisfiable subsets.In:Proc.of the 20th IEEE Real-time and Embedded Technology and Applications Symp.(RTAS 2014).2014.169-178.[doi:10.1109/RTAS.2014.6926000]
    [16] Eldib H, Wang C, Taha M, et al.Quantitative masking strength:Quantifying the power side-channel resistance of software code.IEEE Trans.on Computer-aided Design of Integrated Circuits and Systems, 2015, 34(10):1558-1568.[doi:10.1109/TCAD.2015.2424951]
    [17] Leroy X.Formal verification of a realistic compiler.Communications of the ACM, 2009, 52(7):107-115.[doi:10.1145/1538788.1538814]
    [18] Klein G.Operating system verification-An overview.Sadhana, 2009, 34(1):27-69.[doi:10.1007/s12046-009-0002-4]
    [19] de Moura LM, Bjørner NS.Z3:An efficient SMT solver.In:Ramakrishnan CR, Rehof J, eds.Proc.of the 14th Int'l Conf.on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2008).2008.337-340.[doi:10.1007/978-3-540-78800-3\_24]
    [20] Barrett CW, Conway CL, Deters M, Operating system verification-An overview.CVC4.In:Gopalakrishnan G, Qadeer S, eds.Proc.of the 23rd Int'l Conf.on Computer Aided Verification (CAV 2011).2011.171-177.[doi:10.1007/978-3-642-22110-1\_14]
    [21] Dutertre B.Yices 2.2.In:Biere A, Bloem R, eds.Proc.of the 26th Int'l Conf.on Computer Aided Verification (CAV 2014).2014.737-744.[doi:10.1007/978-3-319-08867-9\_49]
    [22] Cimatti A, Griggio A, Schaafsma BJ, et al.The MathSAT5 SMT solver.In:Piterman N, Smolka SA, eds.Proc.of the 19th Int'l Conf.on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2013).2013.93-107.[doi:10.1007/978-3-642-36742-7\_7]
    [23] Brummayer R, Biere A.Boolector:An efficient SMT solver for bit-vectors and arrays.In:Kowalewski S, Philippou A, eds.Proc.of the 15th Int'l Conf.on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2009).2009.174-177.[doi:10.1007/978-3-642-00768-2\_16]
    [24] Godefroid P, de Halleux J, Nori AV, et al.Automating software testing using program analysis.IEEE Software, 2008, 25(5):30-37.[doi:10.1109/MS.2008.109]
    [25] Beyer D, Keremoglu ME.CPAchecker:A tool for configurable software verification.In:Gopalakrishnan G, Qadeer S, eds.Proc.of the 23rd Int'l Conf.on Computer Aided Verification (CAV 2011).2011.184-190.[doi:10.1007/978-3-642-22110-1\_16]
    [26] Hsu CW, Wah WB, Huang R, et al.Constraint partitioning for solving planning problems with trajectory constraints and goal preferences.In:Veloso MM, ed.Proc.of the 20th Int'l Joint Conf.on Artificial Intelligence (IJCAI 2007).2007.1924-1929.
    [27] Benton J, Coles AJ, Coles A.Temporal planning with preferences and time-dependent continuous costs.In:McCluskey L, Williams BC, Silva JR, et al., eds.Proc.of the 22nd Int'l Conf.on Automated Planning and Scheduling (ICAPS 2012).2012.2-10.
    [28] Edelkamp S, Jabbar S, Nazih M.Large-scale optimal PDDL3 planning with MIPS-XXL.In:Proc.of the 5th Int'l Planning Competition Booklet (IPC 2006).2006.28-30.
    [29] Helmert M.The fast downward planning system.Journal of Artificial Intelligence Research, 2006, 26:191-246.[doi:10.1613/jair.1705]
    [30] Richter S, Westphal M.The LAMA planner:Guiding cost-based anytime planning with landmarks.Journal of Artificial Intelligence Research, 2010, 39:127-177.[doi:10.1613/jair.2972]
    [31] Li J, Zhang L, Pu G, et al.LTLf satisfiability checking.In:Schaub T, Friedrich G, O'Sullivan B, eds.Proc.of the 21st European Conf.on Artificial Intelligence (ECAI 2014).IOS, 2014.513-518.[doi:10.3233/978-1-61499-419-0-513]
    [32] Li J, Pu G, Zhang Y, et al.SAT-based explicit LTLf satisfiability checking.Artificial Intelligence, 2020, 289:Article No.103369.[doi:10.1016/j.artint.2020.103369]
    [33] Fionda V, Greco G.The complexity of LTL on finite traces:Hard and easy fragments.In:Schuurmans D, Wellman MP, eds.Proc.of the 30th AAAI Conf.on Artificial Intelligence (AAAI 2016).2016.971-977.附中文参考文献:
    [14] 陈力, 王永吉, 吴敬征, 等.基于树状线性规划搜索的单调速率优化设计.软件学报, 2015, 26(12):3223-3241.http://www.jos.org.cn/1000-9825/4853.htm[doi:10.13328/j.cnki.jos.004853]
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

陆旭,于斌,段振华,王德奎,陈矗,崔进.智能规划中面向简单偏好的高效求解方法.软件学报,2023,34(7):3099-3115

复制
分享
文章指标
  • 点击次数:1085
  • 下载次数: 3747
  • HTML阅读次数: 2506
  • 引用次数: 0
历史
  • 收稿日期:2022-09-04
  • 最后修改日期:2022-10-08
  • 在线发布日期: 2022-12-30
  • 出版日期: 2023-07-06
文章二维码
您是第19728195位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号