由于人们对于从繁重的简单劳动中解放的需求,服务机器人成为近来研究的热点项目。服务机器人的研究包含了多方面的技术,其中自然语言理解主要负责解决人机交互问题,为人类和机器人的沟通提供便利的手段。而任务规划则有助于提高机器人的运行效率,使得其更快速、更准确地完成人类对其下达的指令。本文为服务机器人设计了一种自然语言理解算法和一种任务规划算法,其中采用依存语法与配价理论作为自然语言理解算法,改进的进化算法作为任务规划算法。并通过家庭服务机器人仿真比赛平台进行实现,验证算法的有效性；且通过与其他比赛队伍算法效果的对比,验证其优越性。具体内容如下：首先,本文阐述了自然语言理解和机器人任务规划的一些基本方法,对其发展现状进行了描述,并说明了这两项技术在服务机器人中的意义。之后针对本文采用的算法——依存语法与配价理论,以及进化算法进行深入的解析,找出其特点和优劣,分析其对服务机器人应用环境的适应能力。其次,将依存语法与配价理论应用于服务机器人的自然语言理解当中。以家庭服务机器人仿真比赛平台的自然语言理解要求为例,分析其词汇句型特点,总结归纳其词汇常用法,根据依存语法与配价理论的思想建立了配价词汇表,并依靠配价词汇表确定句子的依存结构,实现了祈使句以及陈述句两种类型的自然语言和机器语言之间的转化。再次,改进了传统的进化算法,使其适用于机器人任务规划问题的解决。本文针对任务规划的特点,建立了新的编码结构,使得染色体上的基因可以表示任务规划中的“事件”,从而通过改变染色体的结构来改变完成任务的方法。同时本文改变了传统进化算法的异体同位交叉和随机变异进化方式,采取了自体异位交叉和受限选择变异来解决任务规划中的“事件”顺序和物品选择问题。并且,本文加入了筛选的概念,可以在评价前预先消除不符合逻辑规则的个体,从而提高了运算效率和结果准确性；同时设计了适应度函数,用于评价个体的适应度,也就是该规划的规划效果优劣程度,从而决定了个体的淘汰。最后,本文分别对两个算法进行举例说明,并通过一定量的家庭服务机器人仿真比赛题目来验证其有效性,再同其他参赛队伍的比赛结果进行统计对比分析,验证了算法的优越性,并且在2012年的家庭服务机器人仿真比赛中应用了本文中的算法,证明了其在实际比赛中也有着良好的比赛效果。