Localizing Complex Terrain for Quadruped Robots using Adaptive Submodularity

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：28

、訪客IP：18.217.67.16

姓名

張軒旗(Hsuan-Chi Chang) 查詢紙本館藏

畢業系所

數學系

論文名稱

Localizing Complex Terrain for Quadruped Robots using Adaptive Submodularity
(Localizing Complex Terrain for Quadruped Robots using Adaptive Submodularity)

相關論文

★ 3D Map Exploration and Search using Topological Fourier Sparse Set	★ 次模深度壓縮感知用於空間搜尋
★ Evasion and Pursuit Games via Adaptive Submodularity	★ Learning Spatial Search and Map Exploration using Adaptive Submodular Inverse Reinforcement Learning
★ Maximal Coverage Problems with Routing Constraints using Cross-Entropy Monte Carlo Tree Search	★ 使用成本效益生成樹的資訊軌跡規劃
★ Map Explorations via Dynamic Tree-Structured Graph

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2025-2-3以後開放)

摘要(中)

近年以來，多足機器人的運動學已被廣泛研究。該研究領域的主
要問題在於環境的不確定性。為了解決這個問題，本研究提出了一
種稱為Adaptive Submodularity with Hypothesis Pruning(ASHP)的方
法，將不規則地形上的運動問題重新定義為覆蓋Perlin Noise領域中的
問題。多足機器人能夠在沒有外部感受器的情況下，漸漸地適應在復
雜地形上的運動。Adaptive Submodularity在本文中被應用於預測地
形的樣貌，並提供相關的理論保證值。模擬和實驗顯示出本文提出的
方法相比於Random Selection有更小的預測誤差，且相較於其他的模
型(RMA)有更高的成功率及穩定性。

摘要(英)

The locomotion of the legged robot has been widely researched in
recent years. The main issue in this research area is environmental uncertainty.
To overcome this issue, this research proposed a method called
Adaptive Submodularity with Hypothesis Pruning(ASHP), which reformulates
the locomotion problem on irregular terrains as the coverage
problem in the Perlin domain. The legged robot is able to adaptively
select locomotion over complex terrains without exteroceptive sensors.
The adaptive submodularity is utilized to predict the terrain with theoretical
guarantees. The simulations and experiments demonstrate that
the proposed approach has less prediction error and a higher success
rate than the benchmark, the experiments also show that ASHP is more
robust than the benchmark method(RMA).

關鍵字(中)

★ 次模性
★ 多足運動
★ 最大覆蓋問題
★ 觸摸定位

關鍵字(英)

★ Submodularity
★ Legged Locomotion
★ Maximal coverage problem
★ Touch Localization

論文目次

摘要.................................................................................................... i
Abstract.............................................................................................. ii
Acknowledgements .............................................................................. iii
Contents ............................................................................................. iv
Figures ................................................................................................ vi
Tables .................................................................................................viii
1 Introduction........................................................................ 1
2 Related Work...................................................................... 4
2.1 Legged Locomotion . . . . . . . . . . . . . . . . . . 4
2.1.1 Learning Approaches . . . . . . . . . . . . . . . . . . 4
2.1.2 Zero-Moment Point(ZMP) . . . . . . . . . . . . . . . 5
2.2 Terrain Curriculum . . . . . . . . . . . . . . . . . . 6
2.3 Submodularity . . . . . . . . . . . . . . . . . . . . . 6
2.4 Adaptive Submodularity . . . . . . . . . . . . . . . . 6
3 Background......................................................................... 8
3.1 Submodularity . . . . . . . . . . . . . . . . . . . . . 8
3.2 Adaptive Submodularity . . . . . . . . . . . . . . . . 9
3.3 Hypothesis Pruning . . . . . . . . . . . . . . . . . . 13
3.4 Perlin Noise . . . . . . . . . . . . . . . . . . . . . . 14
3.4.1 Noise Function . . . . . . . . . . . . . . . . . . . . . 15
3.5 Zero-Moment Point (ZMP) . . . . . . . . . . . . . . 16
4 Problem formulation........................................................... 18
4.1 Adaptive Stochastic Submodular Maximization . . . 18
4.2 Coverage function and cost function . . . . . . . . . 18
4.3 Hypothesis on Terrains . . . . . . . . . . . . . . . . 21
5 Proposed algorithms........................................................... 23
6 Experiments........................................................................ 24
6.1 EX1: Terrain Estimation . . . . . . . . . . . . . . . 26
6.1.1 Experimental setup . . . . . . . . . . . . . . . . . . 26
6.1.2 Experiment Result . . . . . . . . . . . . . . . . . . . 26
6.2 EX2: Walking on Complex Terrains . . . . . . . . . 29
6.2.1 Experiment Setup . . . . . . . . . . . . . . . . . . . 29
6.2.2 Experiment Result . . . . . . . . . . . . . . . . . . . 29
6.3 EX3: Walking on Real Terrains . . . . . . . . . . . . 30
6.3.1 Experiment Setup . . . . . . . . . . . . . . . . . . . 30
6.3.2 Experiment Result . . . . . . . . . . . . . . . . . . . 30
7 Conclusions and future work .............................................. 32
References........................................................................................... 33
A Appendix ........................................................................... 40
A.1 Mdog . . . . . . . . . . . . . . . . . . . . . . . . . . 40
A.1.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . 40
A.1.2 Software . . . . . . . . . . . . . . . . . . . . . . . . 40
A.2 Kinematics . . . . . . . . . . . . . . . . . . . . . . . 42
A.2.1 Forward Kinematics . . . . . . . . . . . . . . . . . . 43
A.2.2 Calculation of the hips . . . . . . . . . . . . . . . . . 43
A.2.3 Inverse Kinematics . . . . . . . . . . . . . . . . . . . 43

參考文獻

[1] Zipeng Fu, Ashish Kumar, Ananye Agarwal, Haozhi Qi, Jitendra Malik, and Deepak Pathak. Coupling vision and proprioception for navigation of legged robots. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1727317283, 2022.
[2] Ashish Kumar, Zipeng Fu, Deepak Pathak, and Jitendra Malik. Rma: Rapid motor adaptation for legged robots. arXiv preprint arXiv:2107.04034, 2021.
[3] Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter. Learning quadrupedal locomotion over challenging terrain. Science robotics, 5(47):eabc5986, 2020.
[4] Ken Perlin. An image synthesizer. ACM Siggraph Computer Graphics, 19(3):287296, 1985.
[5] Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Articial Intelligence Research, 42:427486, 2011.
[6] Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Articial intelligence, 101(1-2):99134, 1998.
[7] Alexander W Winkler, C Dario Bellicoso, Marco Hutter, and Jonas Buchli. Gait and trajectory optimization for legged systems through phase-based end-eector parameterization. IEEE Robotics and Automation Letters, 3(3):15601567, 2018.
[8] Shervin Javdani, Matthew Klingensmith, J Andrew Bagnell,
Nancy S Pollard, and Siddhartha S Srinivasa. Ecient touch basedlocalization through submodularity. IEEE International Conference on Robotics and Automation, pages 18281835, 2013.
[9] Claudio Semini, Nikos G Tsagarakis, Emanuele Guglielmino, Michele Focchi, Ferdinando Cannella, and Darwin G Caldwell. Design of hyqa hydraulically and electrically actuated quadruped robot. Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering, 225(6):831849, 2011.
[10] Marc H Raibert. Hopping in legged systemsmodeling and simulation for the two-dimensional one-legged case. IEEE Transactions on Systems, Man, and Cybernetics, (3):451463, 1984.
[11] Hartmut Geyer, Andre Seyfarth, and Reinhard Blickhan. Positive force feedback in bouncing gaits? Proceedings of the Royal Society of London. Series B: Biological Sciences, 270(1529):21732183, 2003.
[12] Ambarish Goswami. Foot rotation indicator (fri) point: A new gait planning tool to evaluate postural stability of biped robots. In Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No. 99CH36288C), volume 1, pages 4752. IEEE, 1999.
[13] Zhijun Li, Quanbo Ge, Wenjun Ye, and Peijiang Yuan. Dynamic balance optimization and control of quadruped robot systems with exible joints. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 46(10):13381351, 2015.
[14] Jian Meng, Yibin Li, and Bin Li. A dynamic balancing approach for a quadruped robot supported by diagonal legs. International Journal of Advanced Robotic Systems, 12(10):142, 2015.
[15] Junmin Li, Jinge Wang, Simon X Yang, Kedong Zhou, and Huijuan Tang. Gait planning and stability control of a quadruped robot. Computational intelligence and neuroscience, 2016, 2016.
[16] Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of articial intelligence research, 4:237285, 1996.
[17] Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and
Chrisina Jayne. Imitation learning: A survey of learning methods. ACM Computing Surveys (CSUR), 50(2):135, 2017.
[18] Honglak Lee, Yirong Shen, Chih-Han Yu, Gurjeet Singh, and Andrew Y Ng. Quadruped robot obstacle negotiation via reinforcement learning. In Proceedings 2006 IEEE International Conference
on Robotics and Automation, 2006. ICRA 2006., pages 30033010. IEEE, 2006.
[19] Deepali Jain, Atil Iscen, and Ken Caluwaerts. Hierarchical reinforcement learning for quadruped locomotion. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 75517557. IEEE, 2019.
[20] Guillaume Bellegarda and Quan Nguyen. Robust quadruped
jumping via deep reinforcement learning. arXiv preprint
arXiv:2011.07089, 2020.
[21] Siddhant Gangapurwala, Alexander Mitchell, and Ioannis Havoutis. Guided constrained policy optimization for dynamic quadrupedal robot locomotion. IEEE Robotics and Automation Letters,
5(2):36423649, 2020.
[22] Xue Bin Peng, Erwin Coumans, Tingnan Zhang, Tsang-Wei Lee, Jie Tan, and Sergey Levine. Learning agile robotic locomotion skills by imitating animals. Robotics: Science and Systems, 2020.
[23] Miomir Vukobratovic and Davor Juricic. Contribution to the synthesis
of biped gait. IEEE Transactions on Biomedical Engineering,
(1):16, 1969.
[24] Jong Hyeon Park and Hoam Chung. Zmp compensation by online trajectory generation for biped robots. In IEEE SMC′99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No. 99CH37028), volume 4, pages 960-965. IEEE, 1999.
[25] Alexander W Winkler, Carlos Mastalli, Ioannis Havoutis, Michele Focchi, Darwin G Caldwell, and Claudio Semini. Planning and execution of dynamic whole-body locomotion for a hydraulic quadruped on challenging terrain. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 51485154. IEEE, 2015.
[26] Shuuji Kajita, Fumio Kanehiro, Kenji Kaneko, Kiyoshi Fujiwara, Kensuke Harada, Kazuhito Yokoi, and Hirohisa Hirukawa. Biped walking pattern generation by using preview control of zero-moment point. In 2003 IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422), volume 2, pages 16201626. IEEE, 2003.
[27] C Dario Bellicoso, Fabian Jenelten, Péter Fankhauser, Christian Gehring, Jemin Hwangbo, and Marco Hutter. Dynamic locomotion and whole-body control for quadrupedal robots. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 33593365. IEEE, 2017.
[28] Yan Jia, Xiao Luo, Baoling Han, Guanhao Liang, Jiaheng Zhao, and Yuting Zhao. Stability criterion for dynamic gaits of quadruped robot. Applied Sciences, 8(12):2381, 2018.
[29] Carlos Gonzalez, Victor Barasuol, Marco Frigerio, Roy Featherstone, Darwin G Caldwell, and Claudio Semini. Line walking and balancing for legged robots with point feet. pages 36493656, 2020.
[30] Yvain de Viragh, Marko Bjelonic, C Dario Bellicoso, Fabian Jenelten, and Marco Hutter. Trajectory optimization for wheeled-legged quadrupedal robots using linearized zmp constraints. IEEE Robotics and Automation Letters, 4(2):16331640, 2019.
[31] Tønnes F Nygaard, Charles P Martin, Jim Torresen, Kyrre Glette, and David Howard. Real-world embodied ai through a morphologically adaptive quadruped robot. Nature Machine Intelligence, 3(5):410419, 2021.
[32] Shamel Fahmi, Carlos Mastalli, Michele Focchi, and Claudio Semini. Passive whole-body control for quadruped robots: Experimental validation over challenging terrain. IEEE Robotics and Automation Letters, 4(3):25532560, 2019.
[33] Jonas Frey, David Hoeller, Shehryar Khattak, and Marco Hutter. Locomotion policy guided traversability learning using volumetric representations of complex environments. arXiv preprint arXiv:2203.15854, 2022.
[34] Ruben M Smelik, Klaas Jan De Kraker, Tim Tutenel, Rafael Bidarra, and Saskia A Groenewegen. A survey of procedural methods for terrain modelling. In Proceedings of the CASA Workshop on 3D Advanced Media In Gaming And Simulation (3AMIGAS), volume 2009, pages 2534. sn, 2009.
[35] Thomas J Rose and Anastasios G Bakaoukas. Algorithms and approaches
for procedural terrain generation-a brief review of current
techniques. In 2016 8th International Conference on Games and Virtual Worlds for Serious Applications (VS-GAMES), pages 12. IEEE, 2016.
[36] Houssam Hnaidi, Eric Guérin, Samir Akkouche, Adrien Peytavie, and Eric Galin. Feature based terrain generation using diusion equation. In Computer Graphics Forum, volume 29, pages 2179 2186. Wiley Online Library, 2010.
[37] Ian Parberry. Modeling real-world terrain with exponentially distributed noise. Journal of Computer Graphics Techniques, 4(2):19, 2015.
[38] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions i. Mathematical programming, 14(1):265294, 1978.
[39] Samir Khuller, Anna Moss, and Joseph Se Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):3945, 1999.
[40] Haifeng Zhang and Yevgeniy Vorobeychik. Submodular optimization with routing constraints. In Proceedings of the AAAI conference on articial intelligence, volume 30, pages 819825, 2016.
[41] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634652, 1998.
[42] Laurence A Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385393, 1982.
[43] Bing-Xian Lu and Kuo-Shih Tseng. 3d map exploration via learning submodular functions in the fourier domain. International Conference on Unmanned Aircraft Systems (ICUAS), pages 11991205, 2020.
[44] Micah Corah and Nathan Michael. Distributed matroid-constrained submodular maximization for multi-robot exploration: Theory and practice. Autonomous Robots, 43(2):485501, 2019.
[45] Andreas Krause and Carlos Guestrin. Near-optimal observation selection using submodular functions. Conference on Artical Intelligence(AAAI) Nectar track, 7:16501654, 2007.
[46] Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, ecient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008.
[47] Oliver Brock, Je Trinkle, and Fabio Ramos. Proofs and experiments in scalable, near-optimal search by multiple robots. Robotics: Science and Systems IV, pages 206213, 2009.
[48] Kaijen Hsiao. Relatively robust grasping. PhD thesis, Massachusetts Institute of Technology, 2009.
[49] Victor Gabillon, Branislav Kveton, ZhengWen, Brian Eriksson, and Shanmugavelayutham Muthukrishnan. Adaptive submodular maximization in bandit setting. Advances in Neural Information Processing Systems, 26, 2013.
[50] Victor Gabillon, Branislav Kveton, ZhengWen, Brian Eriksson, and S Muthukrishnan. Large-scale optimistic adaptive submodularity. In Proceedings of the AAAI Conference on Articial Intelligence, volume 28, 2014.
[51] Ji-Jie Wu and Kuo-Shih Tseng. Adaptive submodular inverse reinforcement learning for spatial search and map exploration. Autonomous Robots, 46(2):321347, 2022.
[52] Marco Hutter, Christian Gehring, Dominic Jud, Andreas Lauber, C Dario Bellicoso, Vassilios Tsounis, Jemin Hwangbo, Karen Bodie, Peter Fankhauser, Michael Bloesch, et al. Anymal-a highly mobile and dynamic quadrupedal robot. In 2016 IEEE/RSJ international conference on intelligent robots and systems (IROS), pages 3844. IEEE, 2016.

指導教授

曾國師(Kuo-Shih Tseng)

審核日期

2023-4-19

推文