HAL多学科开放获取存档中的具有模糊约束和偏好的时间规划

0HAL Id: tel-017292880https://theses.hal.science/tel-017292880于2018年3月12日提交0HAL是一个多学科开放获取存档，用于存储和传播科学研究文档，无论其是否发表。这些文档可以来自法国或国外的教育和研究机构，也可以来自公共或私人研究中心。0HAL多学科开放获取存档，旨在存储和传播法国或国外教育和研究机构、公共或私人实验室发表或未发表的科学研究文档。0具有模糊约束和偏好的时间规划0Krystian Jobczyk0引用此版本：0Krystian Jobczyk. 具有模糊约束和偏好的时间规划. 人工智能[cs.AI]. Normandie Université; AkademiaGórniczo-Hutnicza (Cracovie, Poland), 2017. 英文. �NNT: 2017NORMC259�. �tel-01729288�0获得博士学位0计算机科学专业0在UNICAEN完成0与波兰AGH大学国际合作0论文题目0提交和辩护者0Krystian Jobczyk0论文于2017年12月19日公开发表0评审委员会成员：0Maroua BOUZID教授，卡昂诺曼底大学，论文导师0安东尼∙利格扎教授，克拉科夫科技大学，波兰，论文评审员0BożenaWOZNA-SZCZEŚNIAK女士0教授，切斯托霍瓦大学，波兰，评审员0大卫∙卡马乔教授，马德里自治大学，西班牙，评审员0Marcin SZPYRKA教授，克拉科夫科技大学，波兰，论文评审员0阿卜杜勒-伊拉教授，卡昂诺曼底大学，论文评审员0论文由Maroua Bouzid在GREYC实验室指导0具有模糊约束和偏好的时间规划0                                                    论文10致谢0感谢我的父母对他们的耐心、支持和忍受我不断变化的想法以及对其实现的信任。感谢AntoniLigęza教授的智慧、学术和情感支持，耐心忍受我（有时困难的）个性化，以及为研究自由氛围的创造，使本研究的思想得以成熟，并为我论文的悉心指导。感谢JurkoKarczmarczuk（移民的“叔叔”）提供的全方位支持，大量的学术和生活建议，以及在这项工作的完成上的勇敢监督。感谢我在318/319房间的亲爱的同伴们：Michał、Szymon和Mateusz，以及Krzysio：Kutta和Kluzie -后者在主要和突出的角色中 -为他们创造的友好和家庭氛围，以及在世界各种主题上的思想交流和工作。此外，还要感谢KrzysioKluzie提供的无数工作时间之外的对话和笑话，活跃的记忆和关心，并阅读论文手稿，使我避免了许多疏忽和错误。还要感谢“Adrian教授们”：Weronica和Marek，对我们的博士和生活问题进行了非常友好和真正的智力讨论。感谢Szymon和Michał对他的友谊、支持和远程支持，以及对我的进展的支持。感谢Kuba提供的愉快时光，这常常与他对工作和计算机科学特性的理解有关。0我要感谢Maroua - 我的导师 -在我开始和结束期间对我的支持，以及对我来说是生活经历的各种不同经验的组织。我还要感谢MAD的成员们，在我在Caen期间的工作组会议上的讨论和评论。最后，我要感谢我的aumonarie同事们，特别是PereNicalas（尤其是：Charles-Eric，Funny，Paul，JeanBaptiste，Quantin），感谢你们的友善以及在Caen和Herouville-St. Claire期间的时间组织的成千上万的想法。0我要衷心感谢Hannes Leitgeb - 在我在MCMP期间作为年轻科学家的友好导师 -对我计算需求的积极支持和出色的推荐。我还要衷心感谢我的同事MarioHuber，感谢他对我的论文的浓厚兴趣以及在我在2016年夏天在温哥华期间的所有激动人心的对话和美好时光。0我还要感谢乌迪内大学的AngeloMontanari教授，感谢他在ECAI'14会议期间的讨论和科学通信。特别感谢他对Halpern-Shoham逻辑子系统与正则语言之间关系的解释，以及对时间规划混合驱动器的理论构建的启发。0—————————— 献给：————–我的父母，Szymon，Krzysiek，Kuba————————–以及Wojciech Makarewicz博士先生——————20图1：萨尔瓦多∙达利，记忆的坚持0.12.2 PDDL and PDDL+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .370.13 State of the Art and History of Research in this Area . . . . . . . . . . . . . . . . . . . . . . .38IIIntroduction 2: Temporal Constraints, Preferences and Fuzzy TemporalConstraints400.14 Temporal Constraints – a Brief Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .420.15 Qualitative Temporal Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .420.15.1 Point Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .430.15.2 Allen’s Interval Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .430.15.3 Halpern-Shoham Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .450.15.4 State of the Art. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .460.16 Quantitative Temporal Constraints, or Temporal Constrains Satisfaction Problem and itsspecifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .470.16.1 Temporal Constrains Satisfaction Problem – a Detailed Specification . . . . . . . . . .470.16.2 Simple Temporal Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .490.16.3 Preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .500.17 Two Depictions of Fuzzy Temporal Constraints of Allen’s Sort. . . . . . . . . . . . . . . . .5230目录00.1 论文的主题是什么？...800.2 动机...800.3 问题的表述...900.4 论文的目标...1000.5 论文的结构和内容...1100.6 如何阅读论文？...1300.7 论文方法的简要说明...130I 引言 1：时态规划作为经典规划的扩展。人工智能方法 19 0.8 计划和规划...2100.8.1 规划领域、计划、动作和规划问题...2200.9 规划作为图搜索...2700.9.1 规划作为前向搜索...2700.9.2 规划作为反向搜索...3000.10 规划作为可满足性...3100.10.1 单元传播和Davis-Putnam过程...3200.11 带有时态运算符的规划...3300.12 规划语言...3600.12.1 线性时态逻辑（LTL）...360.17.1 Terminological Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .530.17.2 De Cock-Schockaert’s School Approach to Fuzzified Allen’s Relations . . . . . . . . . .560.17.3 Fuzzy Allen’s Relations in Ohlbach’s Integral-based Depiction . . . . . . . . . . . . . .580.17.4 State of the Art and History of Research in this Area. . . . . . . . . . . . . . . . . .641CONTRIBUTIONS: Temporal Planning Problems Approaches: Critique and Taxon-omy671.1Temporal Planning with Fuzzy Constraints and Prefereces:Analysis of Selected Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .681.2The Temporal Travelling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . .721.2.1Informal Defining of TTSP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .721.2.2Formal Definition of TTSP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .731.3Multi-Agent Schedule-Planning Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .771.3.1A Multi-Agent Schedule-Planning Problem – a More Practical Depiction . . . . . . . .771.3.2General Formulation of a Multi-Agent Schedule-Planning Problem . . . . . . . . . . .791.3.3Types of Temporal Constraints of PM-AS-PP . . . . . . . . . . . . . . . . . . . . . . .801.4Multi-Agent Schedule-Planning Problem versus Temporal Traveling Salesman Problem –Their Modeling and Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .832Temporal Planning with Fuzzy Temporal Constraints and Preferences. The Real Analysis-Based Depiction862.1Introductory Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .872.1.1Motivation of Current Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .872.2Mathematical Foundation of the Convolution-based Approach to Fuzzy Allen’s Relations. .882.2.1Motivation of the Convolution-based Approach . . . . . . . . . . . . . . . . . . . . . .882.2.2Terminological Framework of the Discussion . . . . . . . . . . . . . . . . . . . . . . . .892.2.3Mathematical Foundation in Terms of Real and Abstract Analysis . . . . . . . . . . .912.2.4Algebraic Aspects of the Convolution-based Fuzzy Allen’s Relations. . . . . . . . . .972.3Modeling of Fuzzy Temporal Constraints and Preferences. . . . . . . . . . . . . . . . . . . .992.3.1Fuzzy Temporal Constraints in a New Representation. . . . . . . . . . . . . . . . . .992.3.2Preferences in a New Representation.. . . . . . . . . . . . . . . . . . . . . . . . . . . 1052.4Fuzzy Temporal Constraints and Preferences in STRIPS and Davis-Putnam Procedure . . . . 1072.4.1Fuzzy Temporal Constraints and Preferences in STRIPS . . . . . . . . . . . . . . . . . 1072.4.2Towards Temporal-Preferential STRIPS . . . . . . . . . . . . . . . . . . . . . . . . . . 1082.4.3Fuzzy Temporal Constraints and Preferences in Davis-Putnam Procedure . . . . . . . 1112.5Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1143Computable and programming-wise aspects of temporal planning with fuzzy constraintsand preferences1153.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1163.1.1Motivation of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1163.1.2Objective and Novelty of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . 1163.2Computational Aspects of Temporal Planning with Fuzzy Temporal Constrains and Preferences1173.2.1The Extended STRIPS in Use. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1173.2.2Extended Putnam-David Procedure in Use. . . . . . . . . . . . . . . . . . . . . . . . 1203.3Programming-wise Aspects of Multi-Agent Schedule-Planning Problem . . . . . . . . . . . . . 1253.4Concluding remarks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13044Temporal Planning with Fuzzy Temporal Constraints and Preferences.The Logic-based Depiction1314.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1324.1.1Motivation of this Chapter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1324.1.2Objectives and Novelty of this Chapter. . . . . . . . . . . . . . . . . . . . . . . . . . . 1334.1.3The Problem Definition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1344.2Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1344.3Multi-Valued Preferential Logic (MVPL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1364.3.1Multi-Valued Preferential Logic (MVPL) – Syntax . . . . . . . . . . . . . . . . . . . . 1374.3.2Interval-based Semantics for MVPL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1374.4Multi-Valued Preferential Halpern-Shoham logic (PHS) and its Subsystem PHSL . . . . . . . 1394.4.1Multi-Valued Preferential HS-logic (PHS). . . . . . . . . . . . . . . . . . . . . . . . . . 1394.4.2Subsystem PHSL for Preferences and (Delayed) Actions. . . . . . . . . . . . . . . . . . 1404.4.3Modeling of the Salesman Situation from PTSP-problem. . . . . . . . . . . . . . . . . 1414.5Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1435A General Method of the Hybrid Controller Construction for Temporal Planning withPreferences1445.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1455.2Motivation of Current Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1455.2.1Objectives and Novelty of this Chapter. . . . . . . . . . . . . . . . . . . . . . . . . . . 1455.3Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1465.4Problem Formulation and a General Algorithm of the Controller Construction . . . . . . . . . 1485.5The Controller Construction for Temporal Planning. . . . . . . . . . . . . . . . . . . . . . . 1495.5.1From Triangulation to the Finite Transition System (FTS). . . . . . . . . . . . . . . 1495.5.2From FTS System to the First B¨uchi Automaton . . . . . . . . . . . . . . . . . . . . . 1515.5.3From LTL and HSL,D to the Second B¨uchi Automaton . . . . . . . . . . . . . . . . . 1515.5.4Product Automaton AF T S × ALT L,HSD . . . . . . . . . . . . . . . . . . . . . . . . . . 1535.6Part II: Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1545.6.1The Robot Environment and its LTL � HSD,L-specification. . . . . . . . . . . . . . 1545.6.2From LTL ∪ HSL to the Second B´’uchi Automaton. . . . . . . . . . . . . . . . . . . 1565.6.3The Product Automaton. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1575.6.4PROLOG-description of the Product Automaton. . . . . . . . . . . . . . . . . . . . 1615.7Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1616Towards a Synthesis1636.1Integral-based Approach as a Support of the Logical Approach. . . . . . . . . . . . . . . . . 1637Conclusions1677.1Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1677.2Directions of Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1687.2.1List of the Papers of the Author of the Thesis with a Referrence to its Content. . . . . 169A Annexe 1 – Fuzzy Logic of Integrals for Allen’s relations171A.0.2Requirements of the Construction and Notational Remarks. . . . . . . . . . . . . . . . 171A.0.3Syntax.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172A.0.4Semantics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173A.1 The Pavelka-Hajek-style Completeness and Some Metalogical Properties of FCL-FAIR . . . . 175A.2 FCL-FAIR in Finite Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1765A Annexe 2 – Fuzzy Allen’s relations in a convolution-based depiction in algorithms.178A Annex 3 – The STPU Solution in the Integral-based Specification182A.0.1Simple Temporal Problems with Uncertainty (STPUs) . . . . . . . . . . . . . . . . . . 182A.0.2STPPU, or Simple Temporal Problem under Uncertainty with Preferences . . . . . . . 183A.0.3Integrals and Specification of Solution of STPU’s . . . . . . . . . . . . . . . . . . . . . 184A Annexe 4 – Metalogical properties of Preferential Halpern-Shoham Logic (PHS)189A.1 A detailed presentation of fibred semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189A.2 Some Metalogical Results: Model checking Problem for PHSL and Satisfiability . . . . . . . . 190A.3 Satisfiability Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191A.4 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192A Annexe 5 – Proofs of Some Geometric Properties of Robot Environment194A.1 Proof of Some Facts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194A Annexe 6 – Planning as Graph-Search – More Advanced Algorithm196A.0.1Graph Planning and its Short Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 196A.1 Some Formal Properties of STP.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200A Annexe 7 – Lindstrøm Characterizing Theorem and its Simplified Proof203A.1 Terminological Background. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203A.1.1Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203A.1.2Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203A.1.3Two Further Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204A.1.4Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204A.2 Proof of Lindstrøm Theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205A Annex 8–The Chosen Mathematical Concepts Used in the Thesis207A.1 Measure theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207A.2 Probability theory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207A.3 Algebra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2096Abstract.This chapter provides an overview of this PhD-thesis: the thesis motivation, its objectives andits structure. Finally, some road map how to read this thesis is added. All these points are prefaced byexplanatory remarks what is the main thesis focus.0.1What Is the Thesis About?This thesis is aimed at the discussing of temporal planning with fuzzy constraints and preferences. Planningconstitutes one of the form of rational behavior and reasoning – in particular. Intuitively, we often referplanning to a deliberation process that chooses and organizes actions in order to achieve goals that aredesired or required [1, 2, 3]. Actions are executed in a given domain. Making actions often modifies initialdomains.