由于智能规划能应用于很多领域,近年来,智能规划研究得到了飞速的发展,一些学者提出了不确定性规划问题。然而,经典的图规划算法无法解决不确定性规划问题。因此,不确定性规划问题引起了众多智能规划研究者的关注,至今为止,能解决不确定规划问题的规划器有SGP,CFF,PFF等。这其中,最出名的是1998年由Daniel S. Weld,Corin R. Anderson和David E. Smith提出的感知图规划(SGP)。感知图规划算法既有优点也有缺点,它的缺点有算法比较复杂,时间复杂度较高;不具有启发式搜索,搜索是从初始状态出发,搜索可能为真的所有命题,效率较低;这样致使SGP规划器的整体性能很低。为了克服感知图规划的缺点,本文提出了基于启发式搜索的感知图规划算法。本文提出了一种基于启发式搜索的感知图规划算法的新算法。该算法与现有算法不同,采用了FF中使用的启发式方法。同时采纳了FF中使用的放松动作。因此在图扩张阶段,不用处理互斥关系,极大地提高了效率。本文提出的方法提高了规划器的求解能力,对理论和实际应用都有很大的价值。