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

Efficient Approach for Solving Simple Preference in AI Planning

作　　者：陆旭 于斌[1,2] 段振华 王德奎[3] 陈矗 崔进[5] LU Xu;YU Bin;DUAN Zhen-Hua;WANG De-Kui;CHEN Chu;CUI Jin(School of Computer Science and Technology,Xidian University,Xi’an 710071,China;State Key Laboratory of Integrated Service Networks(Xidian University),Xi’an 710071,China;School of Information Science and Technology,Northwest University,Xi’an 710127,China;School of Computer Science,Qufu Normal University,Qufu 273165,China;School of Computer Science,Xi’an Shiyou University,Xi’an 710065,China)

机构地区：[1]西安电子科技大学计算机科学与技术学院,陕西西安710071 [2]综合业务网理论及关键技术国家重点实验室(西安电子科技大学),陕西西安710071 [3]西北大学信息科学与技术学院,陕西西安710127 [4]曲阜师范大学计算机学院,山东曲阜273165 [5]西安石油大学计算机学院,陕西西安710065

出　　处：《软件学报》2023年第7期3099-3115,共17页Journal of Software

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

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

关 键 词：智能规划 简单偏好 SMT 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]