智能规划是当前人工智能领域中极为活跃的一个研究热点,它已广泛应用于自主机器人、航空航天、自然语言理解、知识推理、人机交互、数据挖掘等许多高技术领域。虽然它的一些理论问题与应用问题是世界上公认的难题,但多年来国内外优秀学者一直致力于这一方向的研究,特别是美国卡耐基梅隆大学的A.L.Blum教授和M.L.Furst教授利用规划图分析提出的图规划方法,第一次采用图的方式来解决规划问题,在智能规划领域中取得了革命性进展。近年来,智能规划研究发展飞速。2002年,第三届国际规划竞赛召丌,值得注意的是,这次大赛集中考察了规划系统对时序和数值问题的解决情况。时序规划问题是一类较难的规划问题,但它更接近现实世界的实际问题,因此引起了众多规划研究者的关注,纷纷投入到时序规划的研究中。目前已经有几个基于图规划算法的规划器可以成功地解决时序规划问题,如TGP,TPSY,LPGP。基于图规划的时序规划算法虽然具有很多优点,但也存在一些局限。比如,它的搜索是从初始状态出发,搜索可能为真的所有命题,这样当初始状态中包括很多与目标不相半A:MI-1’JA~rJ昕,或初始状态可应用的动作数量过多而导致规划图过宽时,图规划算法的性能就会急剧下降。为了克服图规划的这一缺点,作者在对时序图规划深入研究的基础上,提出了以目标为导向的时序图规划算法。本文针对规划领域中比较复杂的一类问题——时序规划问题展开研究,对以下内容进行了创新性研究:本文系统地回顾了智能规划的研究历史,深入地介绍了在图规划框架下智能规划的研究工作,同时,全面地展示了智能规划技术的研究现状及未来的发展方向。提出了一种从目标集扩张时序规划图的新算法。该算法与现有算法不同,采用逆向扩张、正向搜索的策略;由于扩张保留了关于目标的信息,实现了动作方案的完全量化。因此在搜索阶段,只搜索相关可用动作的交叉点,减少了搜索代价,极大地提高搜索效率。这种算法使处理的规划问题从理想向现实迈进了一步,因此在解决实际问题中,具有其独特的优势。由于智能规划技术本身的独立性,开展对智能规划算法的研究,对于竞赛机器人、游戏角色设计、智能用户接口的设计、自然语言理解以及多Agent系统等许多领域的研究也有广泛的应用前景。