當前，利用移動設備為用戶提供更加豐富和完善的服務已成為移動計算領域的研究熱點，而基于位置的服務（location based service，簡稱LBS）就是其中之一，基于GPS的室外導航已經普及．LBS開始進入到大型綜合寫字樓或開放式大型商場的導航中．眾多的寫字問或開放式貨架縱橫交錯，對于室內導航的精準度提出了很大的挑戰．由于樓宇的屏蔽作用，GPS在室內基本無法工作．因此，如何在樓宇內運用移動設備進行導航，依然是亟待解決的科學問題．導航通常被分為兩個階段：路徑規劃和航位推算．在實際應用中，這兩個階段交替執行．

　　針對基于IMU（inertial measure unit）的航位推算精準度不高與室內樓層間路徑優化困難等問題，首先提出了基于啟發式動態規劃的三維路徑規劃算法A-DP，然后，以最優路徑為約束，改進了HDE算法（SPM-HDE），提高了行進方向的準確度，最后，結合其他IMU導航技術，完成在室內三維空間中的導航．經檢驗，算法效率與航位推算的精確度均有較大提高．