基於混合式 A* 演算法解決差速式機器人於具有狹長通道之環境中執行推箱任務之規劃問題

Solving Box-Pushing Problem in Narrow Passages Environment with Differential-Drive Robot based on Hybrid A* Algorithm

郭冠成(Kuan-Cheng Kuo)

指導教授 ： 詹魁元

國立臺灣大學/工學院/機械工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202203107

摘要

推動為移動式機器人都具備的基本能力，在夾具無法應用的情境中，推動便是一種移動式機器人重要的搬運策略。而推箱任務屬於移動式機器人搬運任務中的經典問題之一，任務的達成會與推動的預測模型、推動策略、和推動規劃有關。
本研究便是在探討差速式機器人在具有狹長通道的環境中，能否順利完成推動規劃，找出可行的推動路線。窄口或狹長通道為實務環境中經常出現的空間特徵，像是：倉儲、病房...等室內環境，如何順利通過與機器人的規劃密不可分。然而多數的研究是依靠局部規劃，即時更新推動方向，並沒有在全域規劃時便考量換邊行為的可能性，因此導致推動的效率不佳，甚至可能因為缺乏全域規劃的路徑，使機器人將箱子推至死路，導致任務失敗。
為解決此問題，本研究採取穩定推動（stable pushing）為推動策略，並提出一種基於 Hybrid A* 演算法的全域規劃方法解決差速式機器人在具有狹長通道的室內環境中，執行推箱時所面臨的規劃問題。透過修改 Hybrid A* 的節點擴展方式，並加入朝向預測的機制，此演算法能夠規劃出具有換邊行為的推動路線。最後於模擬的環境中，顯示該演算法，在較複雜、具有多個狹長通道的環境中，
仍可以完成推箱任務的規劃，找出通過通道抵達終點的可行路線。

關鍵字

移動式機器人 ； 推箱任務 ； 路徑規劃 ； Hybrid A*

並列摘要

Pushing is one of the basic capabilities that all mobile robots have. In some situations, when the robots cannot use the gripper to manipulate the object, pushing can be considered a good transport strategy. Box-pushing problem is one of the classic problems in mobile robot transportation. To solve the problem, it will be related to the model prediction, the pushing strategy, and the motion planning. Most research relies on local planning to make switch sides choices, but not global planning. It causes the pushing path to be inefficient when there are narrow passages in the environment. Sometimes, robots will push the box to a dead end because lacking global planning to plan the right path. Therefore, our research uses stable pushing as the pushing strategy and proposes a global planning method based on the Hybrid A* algorithm. By modifying the node expansion method of the Hybrid A* and adding a direction prediction mechanism, to make the algorithm can find a path with switch side behavior. In the simulation, the algorithm is validated and can deal with more complex environments with narrow passages. This improves the ability of the robot to solve the box-pushing problem.

並列關鍵字

Mobile robot ； Box-pushing problem ； Path planning ； Hybrid A*

參考文獻

[1] D. B. Poudel, “Coordinating hundreds of cooperative, autonomous robots in a warehouse,” Jan, vol. 27, no. 1-13, p. 26, 2013.

[2] E. Marder-Eppstein, E. Berger, T. Foote, B. Gerkey, and K. Konolige, “The office marathon: Robust navigation in an indoor office environment,” in 2010 IEEE international conference on robotics and automation, pp. 300–307, IEEE, 2010.

[3] R. Siegwart, I. R. Nourbakhsh, and D. Scaramuzza, Introduction to autonomous mobile robots. MIT press, 2011.

[4] S. Thrun, W. Burgard, and D. Fox, “A real-time algorithm for mobile robot mapping with applications to multi-robot and 3d mapping,” in Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), vol. 1, pp. 321–328, IEEE, 2000.

[5] A. Leigh, J. Pineau, N. Olmedo, and H. Zhang, “Person tracking and following with 2d laser scanners,” in 2015 IEEE international conference on robotics and automation (ICRA), pp. 726–733, IEEE, 2015.