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

作者简介:

陆旭(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:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    智能规划(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.

    参考文献
    相似文献
    引证文献
引用本文

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

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

京公网安备 11040202500063号