- Al Reasoning Methods for Robotics
Joachim Hertzberg, Raja Chatila
Artificial intelligence (Al) reasoning technology involving, e.g., inference, planning, and learning, has a track record with a healthy number of successful applications. So, can it be used as a toolbox of methods for autonomous mobile robots? Not necessarily, as reasoning on a mobile robot about its dynamic, partially known environment may differ substantially from that in knowledge-based pure software systems, where most of the named successes have been registered.
This Chapter sketches the main robotics- relevant topics of symbol-based Al reasoning. Basic methods of knowledge representation and inference are described in general, covering both logic- and probability-based approaches. Then, some robotics-related particularities are addressed specially: issues in logic-based high-level robot control, fuzzy logics, and reasoning under time constraints. Two generic applications of reasoning are then described in some detail: action planning and learning.
General reasoning is currently not a standard feature onboard autonomous mobile robots. Beyond sketching the state of the art in robotics- related Al reasoning, this Chapter points to the involved research problems that remain to be solved towards that end.
The Chapter first reviews knowledge representation and deduction in general (Sect. 9.1), andthen goes into some detail regarding reasoning issues that are considered particularly relevant for applications in robots (Sect. 9.2). Having presented reasoning methods, we then enter the field of generic reasoning applications, namely, action planning (Sect. 9.3) and machine learning (Sect. 9.4). Section 9.5 concludes.
Historical debates about the necessity and wisdom of employing symbolic reasoning in autonomous mobile robots notwithstanding, there now seems to be agreement that some part or layer in the control system of such robots should or could include reasoning. Hybrid control architectures (Chap. 8) would be typical software structures for solving the difficult problem of amalgamating their contributions with those of other parts of the controller, while guaranteeing sufficiently short control cycle times, so that the robot can act safely in a dynamic environment.
Symbolic reasoning is understood here in the classical sense of artificial intelligence (AJ), i. e., deliberation based on symbols as in first-order predicate logic(FOPL) or Bayesian probability theory, but typically with restrictions and/or extensions thereof, which have to be traded off against each other to achieve a suitable combination of expressivity and inference speed.
9.1 Knowledge Representation and Inference
Reasoning requires that the reasoner — in our case, a robot — has an explicit representation of parts or aspects of its environment to reason about. Two questions come up immediately: what are suitable formats for such an explicit representation, and where does the represented knowledge come from?
The second question refers to the problem of generating and maintaining in real time a symbolic description of the robotrsquo;s environment, or at least of some part of it, based on a previous symbolic description and on re- cent environment information obtained from sensors and communication with other agents. In full generality, this problem is currently unsolved, involving AI fundamentals such as symbol grounding [9.1] and ob- ject anchoring [9.2]. So practical symbolic reasoning in a robot is restricted to that part of its knowledge that can be kept sufficiently recent. This includes, obviously, static knowledge about the environment, such as the topological elements and their relations in a building; transient knowledge available in symbolic forms, such as in facility management databases; and, most challenging, symbolic data that has to be distilled from sensor data. Object recognition from camera data (Chap. 23) is a relevant method here.
This section deals with answers to the first question, i.e., formalisms suitable for representing knowledge. Suitability has two aspects here that are to be treated as two sides of one coin. One is epistemological adequacy: does the formalism allow the targeted aspects of the environment to be expressed compactly and precisely? The other is computational adequacy: does the formalism allow typical inferences to be drawn effectively and efficiently? There is a trade off between these two adequacies, given that very rich, expressive, and hence epistemologically appealing formalisms are typically accompanied by intractable or even undecidable inference problems, and vice versa. Knowledge representation (KR), then,
is the field of Al that focuses on the design of formalisms that are both epistemologically and computationally adequate for expressing knowledge about a particular domain. [9.3, p. xiii]
In this section, we focus on two families of formalisms, namely, logic and probability theory, and respective inference procedures. For introductions to the field of KR and for sources for recent results, we refer to the general AI and KR literature as given at the end of this chapter. In addition, there is the International Conference on Knowledge Representation (KR), held biannually every even year.
9.1.1 Logic
First-order predicate logic (FOPL) is the archetype of KR formalisms in AI. Having said this, let us add immediately that it does not qualify for such a formalism in the aforementioned sense of being both epistemologically and computationally adequate for typical application do- mains — in many cases, it is neither of the two. However, it is the background for conceptually and mathematically understanding formalisms for representing and reasoning with definite knowledge.
We assume familiarity with the basic notions of FOPL, and rather than giving another sketch here, we refer to the substantial body of textbo
全文共56341字，剩余内容已隐藏，支付完成后下载完整资料
- 机器人的逻辑模式
Joachim Hertzberg, Raja Chatila报道
人工智能(Al)推理技术包括推理、规划和学习，其成功应用数量可观。那么，它可以作为自主移动机器人的工具箱吗?不一定，因为在移动机器人上对其动态的、部分已知的环境的推理可能与基于知识的纯软件系统中的推理有很大的不同，在纯软件系统中，大多数已命名的成功都已注册。
本章概述了基于符号推理的主要机器人相关主题。一般介绍了知识表示和推理的基本方法，包括基于逻辑和基于概率的方法。在此基础上，重点讨论了基于逻辑的高级机器人控制、模糊逻辑和时间约束下的推理等问题。然后详细描述了推理的两种一般应用:行动计划和学习。
一般推理目前还不是机载自主移动机器人的标准功能。除了概述与机器人相关的推理技术的现状外，本章还指出了在这方面有待解决的相关研究问题。
本章首先回顾一般的知识表示和推理(第9.1节)，然后详细讨论与机器人应用特别相关的推理问题(第9.2节)。在介绍了推理方法之后，我们进入了一般推理应用领域，即行动规划(9.3节)和机器学习(9.4节)。9.5节总结道。
关于在自主移动机器人中使用符号推理的必要性和智慧的历史争论，尽管如此，现在似乎一致认为，这些机器人控制系统中的某些部分或层应该或可以包含推理。混合控制结构(第八章)将是典型的软件结构，用于解决将它们的贡献与控制器其他部分的贡献结合起来的难题，同时保证足够短的控制周期时间，使机器人能够在动态环境中安全地工作。
符号推理是在这里理解的经典意义上的人工智能(AJ)，即。在一阶谓词逻辑(FOPL)或贝叶斯概率论中，基于符号的推理，但通常带有限制和/或扩展，这些限制和/或扩展必须相互交换，以实现表达性和推理速度的适当组合。
9.1知识表示与推理
推理要求推理者(在我们的例子中是机器人)对其所处环境的各个部分或方面有一个明确的表示来进行推理。马上就会出现两个问题:对于这种显式表示，什么是合适的格式?所表示的知识从何而来?
第二个问题是基于之前的符号描述和传感器获取的环境信息以及与其他agent的通信，实时生成和维护机器人环境的符号描述，或者至少是其中的一部分。总的来说，这个问题目前尚未解决，涉及到人工智能的基本原理，如符号接地[9.1]和对象锚定[9.2]。因此，机器人的实际符号推理被限制在其知识中能够保持足够近期的那部分。这显然包括对环境的静态知识，例如建筑物的拓扑元素及其关系;以符号形式(如设施管理数据库)提供的瞬时知识;最具挑战性的是必须从传感器数据中提取的符号数据。从相机数据中识别物体(第23章)是一个相关的方法。
本节讨论第一个问题的答案，即，适用于表示知识的形式主义。适用性在这里有两个方面，可以看作是一枚硬币的两面。一个是认识论的充分性:形式主义是否允许环境的目标方面被简洁而精确地表达?另一个是计算充分性:形式主义是否允许有效地绘制典型的推论?这两个不足之间有一个权衡，因为非常丰富的，表达性的，因此认识论上有吸引力的形式主义通常伴随着棘手的，甚至无法决定的推理问题，反之亦然。知识表示(KR)，则
是一个关注形式主义设计的领域，这些形式主义在认识论和计算上都足以表达关于特定领域的知识。(9.3,p .十三世)
在本节中，我们将重点讨论两类形式主义，即逻辑和概率论，以及各自的推理过程。关于KR领域的介绍和最近结果的来源，我们参考本章末尾给出的一般AI和KR文献。此外，还有知识表示国际会议(KR)，每半年甚至每一年举行一次。
9.1.1逻辑
一阶谓词逻辑(FOPL)是人工智能中KR形式主义的原型。说了这一点，让我们立即补充说，它不符合这样的形式主义的上述意义上的认识论和计算上的充分为典型的应用程序做-主要-在许多情况下，这两者都不是。然而，它是概念上和数学上理解形式主义的背景，用于用明确的知识表示和推理。
我们假定您熟悉FOPL的基本概念，这里我们不打算给出另一个概述，而是参考大量教科书和介绍。每一本典型的人工智能教科书都介绍了FOPL，[9.4,5]也不例外。[9.6]是逻辑学的原则引申;[9.7]一个实用的，[9.8]一个简洁的数学。
用某种形式的逻辑表示知识，便于使用可证明的可靠和完整的计算从该知识中进行推断。自动推理是逻辑和人工智能的一个子领域，它提供了大量功能强大的可随时使用的实现推理系统。(见[9.4，第9章]介绍;[9.9]是最近出版的一本全面的源码书。)
依靠逻辑推理，机器人可以推断出大量的事实，否则这些事实可能很难或不可能得到。例如，假设机器人通过获取和解释传感器数据来感知，假设办公大楼的Dso9门当前是关闭的:以某种特定的FOPL语言表示的closed (Ds09)，假设对符号有直观的解释。让我们进一步假设机器人关于建筑的静态知识基础包含这些句子
常数和变量d表示门;表示房间;走廊;变量，表示位置，即，房间和走廊。假设机器人的定位告诉它当前的房间或走廊位置(.)。
然后，假设机器人知道自己在()处，观察Closed()就需要打开()，更有趣的是，只有Open()Open()为真时才能访问()。因此，举例来说，在执行一项送货到房间的任务时，机器人可能会重新规划它的路线，除非已知至少有一个and是关闭的。如果其中一个或两个的状态未知(当前知识库既不开放(.)也不封闭(.))，则既不能证明也不能证明可访问性。这样就可以选择规划路线，并在现场收集所需的状态。
因此，正如这个小例子所示，FOPL是一个强大的表示和推理工具。此外，它的理论很好地理解。特别是，众所周知，FOPL中的推理结果通常是不可判定的，这意味着一个完善的、完整的推理算法甚至不能保证某些特定推理尝试的终止，更不用说快速的结果了。
然而，这并不意味着逻辑作为一种表示和推理工具需要完全处理掉。许多应用程序不需要FOPL的完全表达能力。此外，有许多有趣的FOPL语言子集是可决定的，并且可以通过在大多数实际情况下都是有效的算法来处理。因此，KR社区在识别FOPL子集和拟合推理过程方面做出了一些努力，这些过程在认识论和计算上都符合广泛应用的要求。我们将更详细地考虑其中两个:命题逻辑和描述逻辑。
命题的理论
在相当多的实际案例中，FOPL理论(公式集)实际上代表有限域。从逻辑上讲，它们拥有有限的赫布兰德宇宙，或者至少可以以它们所拥有的形式被重塑。在这种情况下，用FOPL语法表示域理论可能仍然很方便，但是所有超出纯命题理论的地方都只是为了方便注释。例如，一个公理，说明一个机器人一次只能在一个位置(房间或走廊)
是否可以将有限的建筑物夷为平地，以显式地处理所有位置(例如在六层楼的建筑物中)的笨拙但等价的形式
其中谓词的每个基本(无变量)实例，如上面的At实例，都被视为命题变量，与文本标识有关。
这里的好消息是，有限赫布兰德宇宙上与FOPL理论对应的平坦理论是命题;因此，它是可决定的。此外，在某些实际条件下，例如，如果对FOPL理论中的变量进行排序(即，信息是有用的——变量在房间和走廊上的范围)，它甚至可以由更紧凑的FOPL语法机械地生成。
潜在的坏消息是,当然现在命题理论可能包含大量的命题的句子:一般来说,所有组合的变量替换FOPL句子需要生成,域尺寸的增长是multi-exponential FOPL变量。
然而，命题可满足性检查或模型检查技术正在取得长足的进展，允许在常规硬件上以秒级的计算时间处理包含数千甚至数万个变量的命题理论。如果存在许多可满足命题公式的模型，或者许多基本事实的真伪是先验已知的(例如，机器人通过独立定位At())，那么这些方法尤其有效。在实际的KR中，这两种情况经常出现。
[9.4，第七章]介绍了模型检验。有一类方法是基于经典的Davis-Putnam (DPLL)算法[9.10]。它试图系统地构建一个给定理论的命题模型，有效地传播变量的解释约束。另一类算法应用本地搜索技术，试图使用随机(蒙特卡罗)变量赋值生成解释。[9.11]是最近的一组论文，总结了当前的研究现状，其中包括一篇关于SAT2002竞赛结果的论文，该论文详细讨论了最近的可满足性检验器在合成上的性能。，通常不自然地困难)问题。
描述逻辑
描述逻辑(DL)是20世纪70年代出现的一种严格的KR形式，即语义网络和框架系统。从逻辑上讲，DLs是FOPL的一个可判定子集族，其中有一个可比较的变种。
使用DL语言表示关于特定领域的知识有两部分。首先，建立了该领域的本体。介绍了一般的领域概念以及这些概念之间的关系。在所有本体中出现的一种特别有趣的关系类型是超类-子类关系。由于DLs——作为强制可判定性的手段的一部分——严格禁止指定概念之间的循环关系，超类关系对概念施加了层次分类，用于定义属性继承，就像面向对象编程一样。由于历史原因，基于dll的域表示的第一部分通常称为TBox(或术语知识)。
DL语言中的概念对应于一元谓词。举个例子，机器人导航领域的本体可能包括门、位置等概念。概念层次结构是通过定义概念相等=或子概念属性(例如，房间位置和走廊位置)来构建的。概念可以组合使用概念结合,分离,否定(分别为,﹁),允许,例如,概念定义,比如门= ClosedOpen,开放=﹁关闭。
DL语言中的角色对应于二进制谓词，例如门和位置。角色的不一致、交叉和联合按预期定义，这是定义逆角色的一个例子。可以组合角色，例如在定义(位置与if相邻，且仅当某些门指向to时)。最后，可以组合概念和角色来定义新的概念和角色。特别地，它是可能量化的，即。，个别对象(见下文)
可以一致地替换角色参数，例如，可以定义. open(假设操作符具有直观的绑定规则)。DLs的不同变体在它们提供的其他操作符方面有所不同。详见[9.3]。
作为使用DLs表示域的第二部分，必须将单个对象引入概念和角色语言。域表示的这一部分称为ABox或断言知识，例如，可以断言Room()、(、)和Closed()。
DLs提供许多推理服务，这些服务基于给定TBox和ABox中的逻辑推理。它们包括概念定义的一致性、概念的包容和分解性、ABox相对于TBox的一致性、概念和角色实例，所有这些都可以在DL中确定。根据上面的TBox和ABox基础知识，可以得出这样的结论:一切都是一致的，并且()(注意，这里只知道通向哪扇门)。这些DL推理在理论上是难以处理的，但在大多数实际情况下运行得非常有效。
参考文献[9.3]提供了DL技术的全面概述。2004年，万维网联盟(W3C)将web本体语言(web ontology language, OWL)[9.12]定义为语义web的技术基础。语言的一部分是OWL-DL，这是刚刚描述的经典DL。OWL-DL本体开始在web上公开可用;有关教程介绍，请参见[9.13]。
9.1.2概率论
基于逻辑的KR形式主义是值得考虑的，无论何时，事实知识是代表，从中作出推论。然而，机器人可能使用的关于其环境的部分知识并没有真正具备这种特性。在KR形式主义中进行选择——就像在编程语言中进行选择一样——在某种程度上取决于品味、经验、熟悉程度或系统集成方面的考虑。在KR术语中，形式主义在某些领域的认识论充分性不是一个可以精确判断的问题。
然而，就某些应用程序类型的KR需求而言，逻辑(至少它的经典变体)有许多弱点。处理不确定性是其中之一，或者更确切地说，是它们的整个家族，因为不确定性本身就是一个超载的概念。缺乏知识是它的一个方面。只要某些事实的真伪尚未确定，逻辑学就可以处理这个问题。然而，如果知识库中有太多未确定的内容，逻辑将不再能够进行有趣的推理，因为逻辑上一切都是可能的。然而，直觉上不同的可能性可能在可能性上有很大的不同。
KR领域采用贝叶斯概率作为这种不确定性的表示和推理方法，使用的是事实之间的相关性，而不是严格意义上的含义。注意，这种方法合并了缺乏精确和完整知识的不同来源。有些知识可能是未知的，因为它在原则上是不可知的，或者因为它被认为过于昂贵，无法建立一个精确的理论或确定所有与做出合理推断相关的信息。在这两种情况下，使用概率而不是二元真值可以作为近似。请注意，真理的概念在这里与在古典逻辑学中仍然是一样的:客观地说，一个事实应该是真或假;概率只是主观程度的模型，相信事实是真的。注意，这与模糊逻辑不同，后者将在下面简要讨论(第9.2.2节)。
与第9.1.1节类似，这里我们假定熟悉概率论的基本概念。参考文献[9.4，第13章]给出了一个很好的基本介绍;为了更全面的处理，有大量的入门教材，其中[9.14]是最近的一个例子。
在贝叶斯概率论中，推理基本上是指在给定其他先验和相关概率的情况下，推断出某一感兴趣事件的概率。实际上，一种重要的概率推理类型是诊断推理:从观察到的结果推理到隐藏的原因，给出指定从原因到结果的条件概率的因果规则。所以问题是，对于潜在的原因C和观察到的结果E:给定先验概率P(C)和P(E)以及条件概率P(E|C)，确定后验P(C|E)。解当然是由贝叶斯规则给出的
然而，就像在逻辑推理中一样，这个理论上有吸引力的原则最终被证明是正确的
如果天真地应用，是不切实际的。考虑到不仅一种效果E可以被观察到，而且n种效果;此外，并非所有这些都是有条件独立的。计算正确后验的贝叶斯规则的广义形式很简单，但是谁能指定所有涉及到的条件概率呢?
直到上世纪80年代末，这个问题或多或少都得到了解决。一种方法是处理E;在不诚实作为独立的，简单地使用n个单独的条件概率并直接使用它们来近似完整的联合概率分布。参考文献[9.4，第14.7章]回顾了这种方法和其他替代方法。
自从出现以来，所使用的解决方案[9.15]就是Bayes networks (BNs)。其思想是在一个有向无环图中表示随机变量，其中一个节点的前面直接有
全文共16874字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[194]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
