《人工智能》实验指导书.doc

贵州大学计算机科学与技术学院 计算机科学与技术科系 本科生 《人工智能》实验指导书/实验教学大纲 王以松 秦 进 2006年9月8日 目 录 实验一 二维网格空间中机器人(绕过障碍物) 3 实验二 模拟实现电梯调度 4 实验三 用遗传算法（演化）求解TSP问题 6 实验四 用A*搜索求解n数码问题 8 实验五 用Prolog求解传教士和野人问题 10 实验六 一阶谓词公式的语法判别系统 12 实验七 子句消解 20 参考资料： 20 实验一 二维网格空间中机器人(绕过障碍物) 实验目的 刺激响应Agent是响应机器中最为典型的一种，它没有内部状态，但它能对所处环境中的外部刺激做出及时响应。对刺激响应Agent行为的探讨，是研究智能机器的第一步。对刺激响应Agent行为的模拟有助于了解智能机器的工作原理、设计思想、构造方法，以加深对智能机器的理解。 实验原理 给定S-R机器人的简单环境，其世界的状态可用特征向量表示。预先给定机器人的目标任务，刺激响应Agen通过感知简单二维世界中的信息，作出简单的动作决策。通过动画演示S-R机器人的动作循环。 在不考虑稠密空间的情况下,机器的状态分为这八种情况. S1 S2 S3 S8 S9 S4 S7 S6 S5 算法: 第一种情况:当机器人处于S1位置时 产生式:S9&&!S4 ----------South 第二种情况:当机器人处于S2位置时 产生式:S9&&!S1 ----------West 第三种情况:当机器人处于S3位置时 产生式:S9&&!S2 ----------West 第四种情况:当机器人处于S4位置时 产生式:S9&&!S3 ----------North 第五种情况:当机器人处于S5位置时 产生式:S9&&!S4 ----------North 第六种情况:当机器人处于S6位置时 产生式:S9&&!S5----------East 第七种情况:当机器人处于S7位置时 产生式:S9&&!S6 ----------East 第八种情况:当机器人处于S8位置时 产生式:S9&&!S1----------South 以上不满足 产生式-----------------North 实验内容 模拟刺激响应Agent在其所处的世界中为完成特定任务所执行的一系列动作。 实验描述及要求 考虑下图所示的二维格子空间世界中的Agent，它的世界被边界完全包围，世界中包含一个大且不能移动的物体，该世界中没有紧凑空间（即边界与物体间的空间仅一个格子宽）。 物体 Agent 要求Agent执行以下行为：走到一个接近边界或物体的格子中，然后沿着此边界（边界的内部或物体的外边界）永远走下去。 实验步骤 理解Agent所应执行的行为。 分析Agent在其所处的世界中所有能执行的动作； 分别刻画每一个动作执行时Agent所处环境的状态的集合。 对每一个状态集合进行抽象，并结合Agent所处世界的状态对抽象结果予以简化。 形式化简化结果，即得到此动作执行的前提条件。 给出所有动作执行所要求的条件，以形成条件与动作之间的映射函数，即为此Agent的行为模型（产生式）。 编程实现此行为模型（最好实现动画演示） 如果可能，进一步考虑动态改变环境（如增加[取出]一个障碍物，增加[移走]一个agent等）。 参考程序 (1)程序实现功能 1两个机器人同时运动； 2机器人沿外边缘顺时针运动，沿障碍物内边缘逆时针运动； 3动态改变运行环境； 4截取图片并实现保存（默认图片文件格式为.jpg）; 5标志稠密空间； 6标志机器人行走路线； 7调节机器人运动速度。 (2) 参考界面 实验二 模拟实现电梯调度 实验目的 掌握产生式系统设计方法，理解状态机的原理。 实验原理 产生式系统是常用的知识表示方法之一，可以用于表示电梯调度的动作函数。状态机的存储器能够存储前一次的输入、特征和动作，利用状态机的原理可以提高电梯调度的效率。 实验内容 设计一个能有效控制电梯的产生式系统（如果电梯内仍有人想要去更高层或者电梯外的更高层仍有人想要乘电梯，该系统却改“上升”为“下降”，则此系统就不能有效控制电梯）。 实验描述及要求 编写练习5.1电梯调度的模拟程序，用动画演示电梯调度过程。 实验步骤 电梯调度算法的产生式系统如下： 感知信息 nStop Go=(x1, …, xn)，xi=true，如果电梯里面有人想去第i层；xi=false，否则。 Ride=(y1, …, yn)，yj=true，如果第j层电梯外面有人想乘电梯；yj=false，否则。 U