《机器人规划问题答案》由会员分享，可在线阅读，更多相关《机器人规划问题答案（3页珍藏版）》请在金锄头文库上搜索。
1、说明：以下内容中，粗斜体的内容是解题的说明而不是答案应该包括的部分。说明：以下内容中，粗斜体的内容是解题的说明而不是答案应该包括的部分。 使用 A*算法求解如下图所示的机器人规划问题， 即： 求解机器人从 （1， 4） 位置运动到 （7， 3）位置的最短路径，其中灰色的位置为障碍物，横方格条纹位置为机器人的初始位置，而 竖条纹的方格为机器人的目标位置。要求画出 A*算法的搜索树，并表明节点扩展的次序。 yx 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 解 ：（解 ：（解题思路：首先需要定义表示机器人所在位置的状态；其次定义算符；再次定义估价解题思路：首先需要定义表示机器
2、人所在位置的状态；其次定义算符；再次定义估价函数，包括函数，包括g(n)和和h(n)，并说明，并说明*( )( )h nh n；最后画出搜索树并表明节点扩展的顺序；最后画出搜索树并表明节点扩展的顺序） 设机器人的状态由二元组（x，y）来表示，其中： 1. x 代表机器人所在位置的横坐标，其取值可为111x； 2. y 代表机器人所在位置的纵坐标，其取值可为15y。 本问题中涉及的算符有四个，分别为 1. 向上移动：U，其效果如下式：( , )U( , 1)x yx y，其中，1y ； 2. 向下移动：D，其效果如下式：( , )D( , 1)x yx y+，其中，5y ； 4. 向右移动：R，
3、效果如下式：( , )R(1, )x yxy+，其中，11x ； 并且，若应用算符以后得到的新状态（x, y）满足下列条件之一时，该算符不能被应用： （1）223xy= ， （2）334xy= ， （3）410 4x y =， （4）1023xy= ， （5）692xy =。（不能让机器人走到障碍物所在的位置不能让机器人走到障碍物所在的位置） 构造估价函数( , )( , )( , )f x yg x yh x y=+，其中( , )g x y表示从初始状态（1，4）(即机器人即机器人在位置（在位置（1，4）)移动到当前状态（x，y）(即机器人在位置（即机器人在位置（x，y）)所需要的步数（其
4、实也其实也就是已经执行的算符的个数就是已经执行的算符的个数） ，而( , )h x y表示状态（x，y）下机器人所在的位置（也就是位也就是位置（置（x，y）同目标位置的 Manhattan 距离，即( , ) |7|3|h x yxy=+。明显地，机器人由状态（x，y）移动到目标状态（7，3）所需要的步数，也就是真实的代价*( , )h x y肯定大于|7|3|xy+，也就是说，对于任意的（x，y） ，有*( , )( , )h x yh x y。所以使用估价函数( , )( , )( , )f x yg x yh x y=+的启发式图搜索算法是 A*算法。 A*算法的搜索树如下图所示，检查并
5、运用算符的次序为 U，D，L 和 R。其中每个节点左边标 明的数字是节点扩展的顺序（让它们生儿子的顺序让它们生儿子的顺序） ，而每个节点（x，y）的右边标明的“a + b”表示的是该节点对应的估价函数值，其中 a = g(x, y) 而 b = h(x, y)。 （下图中的虚线框中的内容是对该搜索树生成过程中的一些细节的说明，正式的答案中不下图中的虚线框中的内容是对该搜索树生成过程中的一些细节的说明，正式的答案中不 应包括这些内容应包括这些内容） U(1, 4)10+7(1, 3)21+6 (1, 5)51+8D(2, 4)31+6R(1, 2)42+7U(2, 5)62+7D(1, 1)123+8U(3, 5)73+6R(4, 5)84+5R(5, 5)95+4R(6, 5)106+3R(7, 5)117+2R(8, 5)8+3R(2, 1)134+7R(3, 1)145+6R(4, 1)6+5R(4, 2)167+4R(3, 2)156+5D(5, 2)8+3R(4, 3)178+3D(5, 3)189+2R(6, 3)1910+1R(7, 3)11+0R
