【麻省理工学院】【常见问题解答】【问题集2_Cognitive Robotics（认知机器人学）】.pdf_大学文库

麻省理工大学 16.412J/6.834J认知机器人问题集#2 截止日期：2005年9月3日星期三课上交背景为了能够在真实环境中智能的、安全的按照人们的意愿进行行动，自主机器人必须具备低速运行时的裤理规划能力，这样，对一些新的规刻算法做性能评估便非常的重要，特别是，相比干一种艺术形式的出现，一种新的算法的在发布之前需要非常细政的性能分断，相应的，一些推理学科也产生了一些实际的得估方法，例如发表一些调查评估的论文或通过诸如人工智能规划竞赛这样的比赛来评价算法的性逢。在评估中。通过使用一系列的通用基准，评估过程会变的简单有效，而这些通用的基准在网上很容易找到，尽管在评估中，我们需要根据不月算法的特性使用不同的性能街标，但一般情况下，我们只需要使用两种常用的性能指标：运行速度和内存占用量。在实际操作中，我们尽量使用独立于处理器的性能折标进行评估。例如，一件系统搜常算法的速度可以用扩展的搜常节点数目来度量，面内存占用量可以用某一时刻搜索路径上的最大节点数来度量。在其他的一些实例中，被拿来比较的算法之间有根大的不同以至于处理器的速度和内存使用量仅仅是一个分母面已。这样，为了描述的更加全面细致，算法的性能通常用包含一系列参数的方程来度量，其中每个参数表征了所解决问题的一个属性，例如，在钓束目标规划中，常用的一个参数就是问题中约束变量所占的比率。目的近几年出现了一类新的推理算法被用来解决有限区线的约束最优化问题，这种算法的特性还没有粮很好的描述，我们熟知的加权约束满足月题（山山dCSP)和最优约束满足问题(optimal CSPs)减是这类算法。我们此次任务的目的线是利月问题2米评估下面三个属于此类的算法，并且整合成一篇针对运行结果的调查报告。要评估的三个算法是：算法A,冲突导向A'搜家(Conflict directed A·Seeh》算法B:基于“银国玩钙"的分支定界搜索(Branch-and-bound using Russian Doll Search) 算法C:分解动态规划(Decomp0 sition and Dynamie Programming）

麻省理工大学 16.412J/6.834J 认知机器人问题集 #2 截止日期：2005 年 9 月 3 日星期三课上交背景为了能够在真实环境中智能的、安全的按照人们的意愿进行行动，自主机器人必须具备低速运行时的推理规划能力。这样，对一些新的规划算法做性能评估便非常的重要。特别是，相比于一种艺术形式的出现，一种新的算法的在发布之前需要非常细致的性能分析。相应的，一些推理学科也产生了一些实际的评估方法，例如发表一些调查评估的论文或通过诸如人工智能规划竞赛这样的比赛来评价算法的性能。在评估中，通过使用一系列的通用基准，评估过程会变的简单有效，而这些通用的基准在网上很容易找到。尽管在评估中，我们需要根据不同算法的特性使用不同的性能指标，但一般情况下，我们只需要使用两种常用的性能指标：运行速度和内存占用量。在实际操作中，我们尽量使用独立于处理器的性能指标进行评估。例如，一种系统搜索算法的速度可以用扩展的搜索节点数目来度量，而内存占用量可以用某一时刻搜索路径上的最大节点数来度量。在其他的一些实例中，被拿来比较的算法之间有很大的不同以至于处理器的速度和内存使用量仅仅是一个分母而已。这样，为了描述的更加全面细致，算法的性能通常用包含一系列参数的方程来度量，其中每个参数表征了所解决问题的一个属性。例如，在约束目标规划中，常用的一个参数就是问题中约束变量所占的比率。目的近几年出现了一类新的推理算法被用来解决有限区域的约束最优化问题，这种算法的特性还没有被很好的描述，我们熟知的加权约束满足问题（valued CSPs）和最优约束满足问题(optimal CSPs)就是这类算法。我们此次任务的目的就是利用问题#2 来评估下面三个属于此类的算法，并且整合成一篇针对运行结果的调查报告。要评估的三个算法是：算法 A：冲突导向 A*搜索（Conflict directed A* Search）算法 B：基于“俄国玩偶”的分支定界搜索（Branch-and-bound using Russian Doll Search）算法 C：分解动态规划（Decomposition and Dynamic Programming）

所要评估的算法的算法提述和相关的参考文献会在下面提供，每个算法要求针对下面提供的一系列基准进行评结，这些基准包括了随机产生的以及真实量界中的不可复杂程度的同题。具体事宜我们费求每两人为一组，共问完成A.B、C中的一个（仅需一个）算法的宾现，或者你可以选择自己独立完成。之后每一组将和另一组成员一起基于常用的基准对两种算法的相对性能进行评估。并写出报。请每个人选好自己的搭档来共同完成算法的实现。我们大致计划每个算法由两组米实现，并会在下周三（二月23日）将算法分配给每一组。在下周上课时，每个人要将自己描档的姓名和忽要实现的算法提交上米。请仔细侧读下面的参考资料米敏出最好的决定，在算法实现过程中。你可以选择任意一种你喜欢的编程语言。对于算法A,我门提供了一个用CC+语言编写的款件集成环境，因此选择算法A的小组需要对CC+语言以及C+ 的接口熟练草握。之后为了比较不同算法的相对性能，我们会将实现不同算法的两个小组进行合并，组成一个“大组”。例如，可以将实暖算法A和算法B的两个小组合并成一个大组，完成两种算法的相对性整评估。算法评估每组的两个同学要在本文提供的每个问避实例上进行算法的实现，问思实例将在本文的末尾提供。注意你的算法不一定能解决所有的付题实例。对于每个可以解决的问题实例，表示出最优解的值。以及所需的运行时间和内存使用量。在不考虑绝对的系统处理时间和内存使用量的条件下，请提出粒立于处理器的算法性能的一些量度和指标（倒如计算搜索树的节点数)并就这些量度报告你的算法的性能。对于每个无法解决的算法实例，指出是由于时间溢出还是内存溢出而导致的.我们要求一个成功的算法实现程序在解决任何算法实例时的运行时间不能超过10分钟

所要评估的算法的算法描述和相关的参考文献会在下面提供。每个算法要求针对下面提供的一系列基准进行评估，这些基准包括了随机产生的以及真实世界中的不同复杂程度的问题。具体事宜我们要求每两人为一组，共同完成 A、B、C 中的一个（仅需一个）算法的实现，或者你可以选择自己独立完成。之后每一组将和另一组成员一起基于常用的基准对两种算法的相对性能进行评估，并写出报告。请每个人选好自己的搭档来共同完成算法的实现。我们大致计划每个算法由两组来实现，并会在下周三（二月 23 日）将算法分配给每一组。在下周上课时，每个人要将自己搭档的姓名和想要实现的算法提交上来。请仔细阅读下面的参考资料来做出最好的决定。在算法实现过程中，你可以选择任意一种你喜欢的编程语言。对于算法 A，我们提供了一个用 C/C++语言编写的软件集成环境，因此选择算法 A 的小组需要对 C/C++语言以及 C++ 的接口熟练掌握。之后为了比较不同算法的相对性能，我们会将实现不同算法的两个小组进行合并，组成一个“大组”。例如，可以将实现算法 A 和算法 B 的两个小组合并成一个大组，完成两种算法的相对性能评估。算法评估每组的两个同学要在本文提供的每个问题实例上进行算法的实现，问题实例将在本文的末尾提供。注意你的算法不一定能解决所有的问题实例。对于每个可以解决的问题实例，表示出最优解的值，以及所需的运行时间和内存使用量。在不考虑绝对的系统处理时间和内存使用量的条件下，请提出独立于处理器的算法性能的一些量度和指标（例如计算搜索树的节点数）并就这些量度报告你的算法的性能。对于每个无法解决的算法实例，指出是由于时间溢出还是内存溢出而导致的。我们要求一个成功的算法实现程序在解决任何算法实例时的运行时间不能超过 10 分钟

每个“大组”要求写一篇比较两种算法性能的评估报告（例如算法A和算法B), 截止日期的上交资料到截止日期时，每个“大组”（即四个学生的一组）需要按里下面的要求，将一份打印形式的报告以及一份电子文档形式的报告交给助教Brian O'Conaill。隐此之外。每个“大组“要将两个算法的实现程序的刚本上之一份，其中包括如何运行算法的简短说明。报告内容每个“大组”需要上交一份报告。报告中应当对每个所实现的算法进行一个教学式的措述，其中要给出一个简单的演示实例。算法描述后景接着要有一个对两种算法的基准值的分析。大组中的每个小组负费各自算法的算法描述，并给出基于基准的算法性佳分析。之后整个大组负责对两种算方法进行比较。为了了解大组中每个人的工作情况，我门要求在报告中要标明每部分的作者姓名，并上交一份反映每个成员所完成工作量的简要说明。具体来讲，每份报告应当包括一下部分： 1.两种算法的描述。给出每个算法的核心思想并给出算法的伪代码。并通过一个简单的教学实例来说明两种算法是如何工作的。 2简要精述你的算法实现，并给出一个针对某个实例运行程序的样本。程序运行样本应当给出最优解以及一些有价值的中间环节。玉.以表格形式给出两种算法在各自基准月题上的运行结果。如果算法白动停止，给出最优解的值和运行时问，香则街出算法是时间溢出还是空间溢出（参考上面有关“算法评估”的部分)， 4,对得到的结果进行讨论：哪种算法在哪个问题上运行得更好？问题实例中影响算法性能的有利和不利因素。你认为每种算法相对于另一种算法的优缺点是什么？扩展算法以产生次优解或所有解的困难程度如何？可否给出一生可能的扩展和政进方法。 5明确每个成员在两种算法的实现以及评估中所做的工作

每个“大组”要求写一篇比较两种算法性能的评估报告（例如算法 A 和算法 B）。截止日期的上交资料到截止日期时，每个“大组”（即四个学生的一组）需要按照下面的要求，将一份打印形式的报告以及一份电子文档形式的报告交给助教 Brian O’Conaill。除此之外，每个“大组“要将两个算法的实现程序的副本上交一份，其中包括如何运行算法的简短说明。报告内容每个“大组”需要上交一份报告。报告中应当对每个所实现的算法进行一个教学式的描述，其中要给出一个简单的演示实例。算法描述后紧接着要有一个对两种算法的基准值的分析。大组中的每个小组负责各自算法的算法描述，并给出基于基准的算法性能分析。之后整个大组负责对两种算方法进行比较。为了了解大组中每个人的工作情况，我们要求在报告中要标明每部分的作者姓名，并上交一份反映每个成员所完成工作量的简要说明。具体来讲，每份报告应当包括一下部分： 1. 两种算法的描述。给出每个算法的核心思想并给出算法的伪代码。并通过一个简单的教学实例来说明两种算法是如何工作的。 2. 简要描述你的算法实现，并给出一个针对某个实例运行程序的样本。程序运行样本应当给出最优解以及一些有价值的中间环节。 3. 以表格形式给出两种算法在各自基准问题上的运行结果。如果算法自动停止，给出最优解的值和运行时间，否则指出算法是时间溢出还是空间溢出（参考上面有关“算法评估”的部分）。 4. 对得到的结果进行讨论：哪种算法在哪个问题上运行得更好？问题实例中影响算法性能的有利和不利因素。你认为每种算法相对于另一种算法的优缺点是什么？扩展算法以产生次优解或所有解的困难程度如何？可否给出一些可能的扩展和改进方法。 5. 明确每个成员在两种算法的实现以及评估中所做的工作

附录：程序源代码的打印形式附在报告的附汝中算法A:冲突导向A搜紫用“冲突导向A*搜常”算法(CDA◆)计算加权约束满足问题(VCSPs)问题的最优解，要用CDA·算法解决VCSP凸问题，你需要编写一个编译器来将VCSP问题转换为最优约束满足问题(OCSP),你可以利川Martin Sachenbacher课上所讲的转换方法米完成两种问题的转换，这种转换还会可引入针对每个状的束的决策变量。接下米，我们通过如下的方法米实现CDA算法，利用一个搜索队列以“最优为先”的顺序列举决策变量的分配，然后检验分配的一致性，并利用在不一致的分配中所铁得的差值来引导瘦索树的展开。正如在Williams和Ragno的论文中描述的那样，CDA算法通过进扩展某个搜常节点的最优子节点和次优兄弟节点面不是扩展所有节点的方式来完成优化子树的扩展，如果你细简化乐的算法实现，你也可以忽略这种改进方法而一次扩展某个搜常节点的所有子节点（当然，我门更希里你使用前各) 为了方便算法的实现，我们提供了一个集成编辑环境，叫做ST,它可以利用一组在命思状志逐辑中表示各个条款的钓束米检测分配的一致性，并且在不一致的时候返回一个差值，命题状态逻辑是命题逻辑的一种，在这种逆辑中所有的命题都被分配给了一组有限域的变量。需要注意的是SAT是用C+来编写的，因此你要么做一个SA灯的外部函数调用来实现算法，要么用C+语言米偏写程序实现算法。为了尽快熟多SAT,我们可以给你一个包含1SAT中CC+代码的CD,称还可以从助教BanO'Coa那里铁得一份ISAT的使用说明。如果你还有任何有关1SAT问题。请直接请教沈曲。参考资料： Brian C.Williams and Robert Ragno:Conflict-directed A+and its Role in Model-based Embedded Systems.To appear in the Special Issue on Theory and Applications of Satisfiability Testing.fowrnal of Discrere Appied Math

附录：程序源代码的打印形式附在报告的附录中算法 A：冲突导向 A*搜索用“冲突导向 A*搜索”算法（CDA*）计算加权约束满足问题（VCSPs）问题的最优解。要用 CDA*算法解决 VCSPs 问题，你需要编写一个编译器来将 VCSP 问题转换为最优约束满足问题（OCSP）。你可以利用 Martin Sachenbacher 课上所讲的转换方法来完成两种问题的转换，这种转换还会引入针对每个软约束的决策变量。接下来，我们通过如下的方法来实现 CDA*算法：利用一个搜索队列以“最优为先”的顺序列举决策变量的分配，然后检验分配的一致性，并利用在不一致的分配中所获得的差值来引导搜索树的展开。正如在 Williams 和 Ragno 的论文中描述的那样，CDA*算法通过进扩展某个搜索节点的最优子节点和次优兄弟节点而不是扩展所有节点的方式来完成优化子树的扩展。如果你想简化你的算法实现，你也可以忽略这种改进方法而一次扩展某个搜索节点的所有子节点（当然，我们更希望你使用前者）。为了方便算法的实现，我们提供了一个集成编辑环境，叫做 ISAT，它可以利用一组在命题状态逻辑中表示各个条款的约束来检测分配的一致性，并且在不一致的时候返回一个差值。命题状态逻辑是命题逻辑的一种，在这种逻辑中所有的命题都被分配给了一组有限域的变量。需要注意的是 ISAT 是用 C++来编写的，因此你要么做一个 ISAT 的外部函数调用来实现算法，要么用Ｃ++语言来编写程序实现算法。为了尽快熟悉 ISAT，我们可以给你一个包含 ISAT 中 C/C++代码的 CD，你还可以从助教 Brian O’Conaill 那里获得一份 ISAT 的使用说明。如果你还有任何有关 ISAT 问题，请直接请教沈曲。参考资料： z Brian C. Williams and Robert Ragno: Conflict-directed A* and its Role in Model-based Embedded Systems. To appear in the Special Issue on Theory and Applications of Satisfiability Testing, Journal of Discrete Applied Math