这是一个理论计算机科学的计划申请书，研究自主机器人控制中提出的问题。我们将研究三个关键的动作算法企划问题, 踏勘问题, 导航问题, 定位问题. 在这三个问题中，机器人必须常常在不明全部知识或在不确定的情况下作出决定（在掌握全部信息时是解决了的）。此类问题被称之为在线算法。如果某算法总能给出接近最优解（即在预知给定问题实例的全部知识后计算出来的解），我们就考虑该在线算法是好的（或具有竞争力的）。如果环境是个图或者一个具有障碍物的多边形，上述三个问题至今还没有好的甚至没有好的随机算法。.在本次申请中，我们将研究踏勘、导航和定位问题的确定和随机算法的竞争性。对于完美机器人的理论上漂亮的算法，往往在实践上，当机器人作不精确的运动和探头的数据模糊时无价值的。因此我们专注于更为实用的机器人算法。我们还将研究若干合作机器人问题的变种。最后我们将运行这些算法以测试其可实用性。