广东工业大学学报 ›› 2021, Vol. 38 ›› Issue (03): 9-16.doi: 10.12052/gdutxb.200127

• • 上一篇    下一篇

时态规划综述及研究现状

饶东宁1, 杨锦鹏1, 刘越畅2   

  1. 1. 广东工业大学 计算机学院，广东 广州 510006;
    2. 嘉应学院 计算机学院，广东 梅州 514015
  • 收稿日期:2020-09-28 出版日期:2021-05-10 发布日期:2021-03-12
  • 通信作者: 杨锦鹏(1995-)，男，硕士研究生，主要研究方向为智能规划，E-mail：420858689@qq.com E-mail:420858689@qq.com
  • 作者简介:饶东宁(1977-)，男，副教授，博士，主要研究方向为智能规划、金融智能
  • 基金资助:
    广东省自然科学基金资助项目(2016A030313700，2016A030313084)

A Survey of Temporal Planning

Rao Dong-ning1, Yang Jin-peng1, Liu Yue-chang2   

  1. 1. School of Computers, Guangdong University of Technology, Guangzhou 510006, China;
    2. School of Computer Science, Jiaying University, Meizhou 514015, China
  • Received:2020-09-28 Online:2021-05-10 Published:2021-03-12

HTML

PDF (PC)

2805

摘要： 作为人工智能领域的一个重要分支, 智能规划被广泛应用于机器人、工业生产、商业应用等领域。时态规划是智能规划的前沿子领域。本文从时态特征、规划方法、应用等三个角度出发, 对时态规划进行综述。与规划能力相比, 时态特征的发展已足够成熟; 基于启发式的状态空间搜索是目前的最佳选择; 研究人员仍在寻找更多更好的应用场景。本文旨在用通俗易懂的方式帮助入门学者快速认识时态规划。

关键词: 人工智能, 智能规划, 时态规划

Abstract: Automated planning is an important branch of artificial intelligence, which can be widely used in robot, industrial production, and commercial fields. A review is conducted on the temporal planning, which is a frontier and sub-area of automated planning, from three aspects: 1) temporal feature; 2) planning method; 3) applications. The conclusions are: 1) comparing with planning ability, the community has proposed sufficient temporal features; 2) for the time being, state space forward searching based on heuristics is our best choice; 3) researchers are still looking for more and better applications. This survey aims to provide basic concepts for students who are interested in temporal planning.

Key words: artificial intelligence, automated planning, temporal planning

中图分类号: 

  • TP182
[1] FIKE R E, NILSSON J N. STRIPS: a new approach to the application of theorem proving to problem solving [J]. Artificial Intelligence, 1971, 2(3-4): 189-208.
[2] PEDNAULT E. ADL: exploring the middle ground between STRIPS and the situation calculus[C]//Proceeding of the First International Conference on Principles of Knowledge Representation and Reasoning. San Francisco: Morgan Kaufmann Publishers Inc, 1989: 324-332.
[3] SMITH D, WELD D S. Temporal planning with Mutual exclusion reasoning[C]//Proceeding of the Sixteenth International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers Inc, 1999: 326-337.
[4] DO M, KAMBHAMPATI S. SAPA: a multi-objective metric temporal planner [J]. Journal of Artificial Intelligence Research, 2003, 20(20): 155-194.
[5] FOX M, LONG D. Fast temporal planning in a Graph plan framework. [C]//Proceedings of AIPS-02 Workshop on Planning for Temporal Domains. Palo Alto, CA: AAAI Press, 2002: 9-17.
[6] SMITH D E, FRANK J, JONSSON A, et al. Bridging the gap between planning and scheduling [J]. Knowledge Engineering Review, 2000, 15(1): 47-83.
[7] FOX M, LONG D. PDDL2.1: an extension to PDDL for expressing temporal planning domains [J]. Journal of Artificial Intelligence Research, 2003, 20: 61-124.
[8] EDELKAMP S, HOFFMANN J. PDDL2.2: The language for the classical part of the fourth international planning competition[R]. Palo Alto, CA: AAAI Press, 2004.
[9] 饶东宁, 蒋志华, 姜云飞. 规划领域定义语言的演进综述[J]. 计算机工程与应用, 2010, 46(22): 23-25.
RAO D N, JIANG Z H, JIANG Y F. Review on evolution of planning domains definition language [J]. Computer Engineering and Applications, 2010, 46(22): 23-25.
[10] GEREVINI A, LONG D. Plan constraints and Preferences in PDDL3: the language of the fifth international planning[R]. Italy: University of Brescia, 2005.
[11] FOX M, LONG D. PDDL+level5: an extension to PDDL2.1 for modeling planning domains with Continuous time-dependent effects[C]//Proceedings of the Third International NASA Workshop on Planning and Scheduling for Space. Palo Alto, CA: AAAI Press, 2003: 1-48.
[12] EYERICH P, MATTMULLER R, ROGER G. Using the context enhanced additive heuristic for temporal and numeric planning[C]//Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling. Palo Alto, CA: AAAI Press, 2009: 130-137.
[13] VIDAL V. The YAHSP planning system: forward heuristic search with lookahead plans analysis[C]//Proceedings of the Fourth International Planning Competition. Palo Alto, CA: AAAI Press, 2004: 56-58.
[14] SCHWARTZ P, POLLACK M E. Planning with Disjunctive temporal constraints[C]//Proceedings of ICAPS-'04 Workshop on Integrating Planning into Scheduling. PaloAlto, CA: AAAI Press, 2004: 67-74.
[15] SAPENO O, MARZAL E, ONAINDIA E. TFLAP: a Temporal forward partial-order planner[EB/OL]. (2018-06-29)[2020-11-17]. https://ipc2018.bitbucket.io/#temporal
[16] 柴啸龙, 姜云飞, 陈蔼祥. 基于规划图的蚁群规划算法[J]. 计算机研究与发展, 2009, 46(9): 1471-1479.
CHAI X L, JIANG Y F, CHEN A X. Ant colony planning algorithm based on planning graph [J]. Journal of Computer Research and Development, 2009, 46(9): 1471-1479.
[17] 伍丽华, 姜云飞, 陈蔼祥. 规划图框架下用遗传算法求解时态规划问题[J]. 计算机研究与发展, 2008, 45(6): 981-990.
WU L H, JIANG Y F, CHEN A X. Using genetic algorithm to solve temporal planning problems under the framework of the planning graph [J]. Journal of Computer Research and Development, 2008, 45(6): 981-990.
[18] FURELOS-BALANCO D, JONSSON A. CP4TP: a Classical planning for temporal planning portfolio [EB/OL]. (2018-06-29)[2020-11-17]. https://ipc2018.bit-bucket.io/#temporal
[19] RANKOOH M F, GHASSEM-SANI G. ITSAT: an efficient SAT-based temporal planner [J]. Journal of Artificial Intelligence Research, 2015, 53: 541-632.
[20] 伍丽华, 姜云飞, 陈蔼祥, 等. 时态规划中基于CSP技术的时态约束方法[J]. 计算机学报, 2012, 35(8): 1759-1766.
WU L H, JIANG Y F, CHEN A X, et al. ACSP-based approach for temporal constraints in temporal planning [J]. Chinese Journal of Computer, 2012, 35(8): 1759-1766.
[21] 刘越畅. 基于动态约束满足框架的强表达时态规划算法[J]. 计算机科学, 2012, 39(6): 226-230.
LIU Y C. Expressive temporal planning algorithm under dynamic constraint satisfaction framework [J]. Computer Science, 2012, 39(6): 226-230.
[22] GIGANTE N. Timeline-based planning: expressiveness and complexity[D]. Udine: University of Udine, 2019.
[23] 白丽赟, 胡学敏, 宋昇, 等. 基于深度级联神经网络的自动驾驶运动规划模型[J]. 计算机应用, 2019, 39(10): 2870-2875.
BAI L Y, HU X M, SONG S, et al. Motion planning model based on deep cascaded neural network for autonomous driving [J]. Journal of Computer Applications, 2019, 39(10): 2870-2875.
[24] TOYER S, TREVIZAN F, THIEBAUX, SYLVIE, et al. ASNets: deep learning for generalised planning [J]. Journal of Artificial Intelligence Research, 2020, 68: 1-68.
[25] COOPER M C, MARIS F, REGNIER P. Monotone temporal planning: tractability, extension and applications [J]. Journal of Artificial Intelligence Research, 2014, 50: 447-485.
[26] SMITH S J J, NAU D S, THROOP T A. Computer bridge: a big win for AI planning [J]. AI Magazine, 1998, 19(2): 93-106.
[27] FERNANDEZ-OLIVARES J, PEREZ R. Driver activity recognition by means of temporal HTN planning[C]//Proceedings of the International Conference on Automated Planning and Scheduling. Palo Alto, CA: AAAI Press, 2020: 375-383.
[28] 冯宇轩. 时间相关的分层任务网络规划[D]. 长春: 吉林大学, 2016.
[29] CARRENO Y, PAIRET È, PETILLOT Y, et al. A decentralised strategy for heterogeneous AUV missions via goal distribution and temporal planning[C]//Proceedings of the International Conference on Automated Planning and Scheduling. Palo Alto, CA: AAAI Press, 2020: 431-439.
[30] KIAM J J, SCALA E, JAVEGA M R, et al. An AI-based planning framework for HAPS in a time-varying environment[C]//Proceedings of the International Conference on Automated Planning and Scheduling. Palo Alto, CA: AAAI Press, 2020: 412-420.
[1] 崔铁军, 李莎莎. 人工智能与生产过程中本质安全的实现[J]. 广东工业大学学报, 2021, 38(06): 84-90.
[2] 胡斌, 周颖慧, 陶小梅. 情感智能与心理生理计算[J]. 广东工业大学学报, 2021, 38(04): 1-8.
[3] 汪培庄, 曾繁慧, 孙慧, 李兴森, 郭建威, 孟祥福, 何静. 知识图谱的拓展及其智能拓展库[J]. 广东工业大学学报, 2021, 38(04): 9-16.
[4] 崔铁军, 李莎莎. 基于因素驱动的东方思维人工智能理论研究[J]. 广东工业大学学报, 2021, 38(01): 1-4.
[5] 邱明晋, 陈璟华, 唐俊杰. 含风电场最优潮流及其关键技术研究综述[J]. 广东工业大学学报, 2018, 35(02): 63-68,94.
[6] 黄苑虹； 梁慧冰； . 从倒立摆装置的控制策略看控制理论的发展和应用[J]. 广东工业大学学报, 2001, 18(3): 49-53.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发