“Implicit Swept Volume SDF: Enabling Continuous Collision-free Trajectory Generation for Arbitrary Shapes”
Conference:
Type(s):
Title:
- Implicit Swept Volume SDF: Enabling Continuous Collision-free Trajectory Generation for Arbitrary Shapes
Presenter(s)/Author(s):
Abstract:
Our innovative approach to trajectory generation seamlessly navigates the complexities of continuous collision avoidance for objects in challenging environments. Leveraging the Swept Volume Signed Distance Field, our hierarchical pipeline outperforms traditional methods by deftly handling non-convex geometries without sacrificing solution space or succumbing to the tunnel effect.
References:
[1]
Denis Blackmore and Ming C Leu. 1992. Analysis of swept volume via Lie groups and differential equations. The International Journal of Robotics Research 11, 6 (1992), 516–537.
[2]
Denis Blackmore, Ming C Leu, and Liping P Wang. 1997. The sweep-envelope differential equation algorithm and its application to NC machining verification. Computer-Aided Design 29, 9 (1997), 629–637.
[3]
Jerry W Blankenship and James E Falk. 1976. Infinitely constrained optimization problems. Journal of Optimization Theory and Applications 19 (1976), 261–281.
[4]
Tyson Brochu, Essex Edwards, and Robert Bridson. 2012. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–7.
[5]
Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. 2020. Fast and robust mesh arrangements using floating-point arithmetic. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–16.
[6]
Wenchao Ding, Lu Zhang, Jing Chen, and Shaojie Shen. 2019. Safe Trajectory Generation for Complex Urban Environments Using Spatio-Temporal Semantic Corridor. IEEE Robotics and Automation Letters 4, 3 (2019), 2997–3004.
[7]
Christer Ericson. 2004. Real-time collision detection. Crc Press.
[8]
Matthias Faessler, Antonio Franchi, and Davide Scaramuzza. 2017. Differential flatness of quadrotor dynamics subject to rotor drag for accurate tracking of high-speed trajectories. IEEE Robotics and Automation Letters 3, 2 (2017), 620–626.
[9]
Xinjian Fan, Xiaoguang Dong, Alp C Karacakol, Hui Xie, and Metin Sitti. 2020. Reconfigurable multifunctional ferrofluid droplet robots. Proceedings of the National Academy of Sciences 117, 45 (2020), 27916–27926.
[10]
Philip L Frana and Thomas J Misa. 2010. An interview with edsger w. dijkstra. Commun. ACM 53, 8 (2010), 41–47.
[11]
Shuang Geng, Qianhao Wang, Lei Xie, Chao Xu, Yanjun Cao, and Fei Gao. 2023. Robo-Centric ESDF: A Fast and Accurate Whole-Body Collision Evaluation Tool for Any-Shape Robotic Planning. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 290–297.
[12]
James Guthrie. 2022. A Differentiable Signed Distance Representation for Continuous Collision Avoidance in Optimization-Based Motion Planning. In 2022 IEEE 61st Conference on Decision and Control (CDC). IEEE, 7214–7221.
[13]
Peter E Hart, Nils J Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4, 2 (1968), 100–107.
[14]
Kris Hauser. 2021. Semi-infinite programming for trajectory optimization with non-convex obstacles. The International Journal of Robotics Research 40, 10–11 (2021), 1106–1122.
[15]
Lucas Janson, Edward Schmerling, Ashley Clark, and Marco Pavone. 2015. Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions. The International journal of robotics research 34, 7 (2015), 883–921.
[16]
Bert J?ttler and Michael G Wagner. 1996. Computer-aided design with spatial rational B-spline motions. (1996).
[17]
Jean-Claude Latombe. 2012. Robot motion planning. Vol. 124. Springer Science & Business Media.
[18]
Steven LaValle. 1998. Rapidly-exploring random trees: A new tool for path planning. Research Report 9811 (1998).
[19]
Changliu Liu, Chung-Yen Lin, and Masayoshi Tomizuka. 2018. The convex feasible set algorithm for real time optimization in motion planning. SIAM Journal on Control and optimization 56, 4 (2018), 2712–2733.
[20]
Dong C Liu and Jorge Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Mathematical programming 45, 1–3 (1989), 503–528.
[21]
Sikang Liu, Michael Watterson, Kartik Mohta, Ke Sun, Subhrajit Bhattacharya, Camillo J. Taylor, and Vijay Kumar. 2017. Planning Dynamically Feasible Trajectories for Quadrotors Using Safe Flight Corridors in 3-D Complex Environments. IEEE Robotics and Automation Letters 2, 3 (2017), 1688–1695.
[22]
Zo? Marschner, Silvia Sell?n, Hsueh-Ti Derek Liu, and Alec Jacobson. 2023. Constructive Solid Geometry on Neural Signed Distance Fields. In SIGGRAPH Asia 2023 Conference Papers. 1–12.
[23]
Ralph R Martin and PC Stephenson. 1990. Sweeping of three-dimensional objects. Computer-Aided Design 22, 4 (1990), 223–234.
[24]
Daniel Mellinger and Vijay Kumar. 2011. Minimum snap trajectory generation and control for quadrotors. In 2011 IEEE international conference on robotics and automation. IEEE, 2520–2525.
[25]
Jorge Nocedal and Stephen J Wright. 1999. Numerical optimization. Springer.
[26]
Inigo Quilez. 2018. Interior SDFs. https://iquilezles.org/articles/interiordistance/. Accessed: 2023-09-13.
[27]
Evgeni? I?A?kovlevich Remez. 1962. General computational methods of Chebyshev approximation: The problems with linear real parameters. US Atomic Energy Commission, Division of Technical Information.
[28]
Silvia Sell?n, Noam Aigerman, and Alec Jacobson. 2021. Swept volumes via spacetime numerical continuation. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–11.
[29]
Silvia Sell?n, Christopher Batty, and Oded Stein. 2023. Reach For the Spheres: Tangency-aware surface reconstruction of SDFs. In SIGGRAPH Asia 2023 Conference Papers. 1–11.
[30]
Oliver Stein. 2012. How to solve a semi-infinite optimization problem. European Journal of Operational Research 223, 2 (2012), 312–320.
[31]
Bolun Wang, Zachary Ferguson, Teseo Schneider, Xin Jiang, Marco Attene, and Daniele Panozzo. 2021. A large-scale benchmark and an inclusion-based algorithm for continuous collision detection. ACM Transactions on Graphics (TOG) 40, 5 (2021), 1–16.
[32]
WP Wang and KK Wang. 1986. Geometric modeling for swept volume of moving solids. IEEE Computer graphics and Applications 6, 12 (1986), 8–17.
[33]
Zhepei Wang, Xin Zhou, Chao Xu, and Fei Gao. 2022. Geometrically constrained trajectory optimization for multicopters. IEEE Transactions on Robotics 38, 5 (2022), 3259–3278.
[34]
Dustin J Webb and Jur Van Den Berg. 2013. Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics. In 2013 IEEE international conference on robotics and automation. IEEE, 5054–5061.
[35]
John D Weld and Ming C Leu. 1990. Geometric representation of swept volumes with application to polyhedral objects. The International Journal of Robotics Research 9, 5 (1990), 105–117.
[36]
Tingrui Zhang, Jingping Wang, Chao Xu, Alan Gao, and Fei Gao. 2023. Continuous Implicit SDF Based Any-Shape Robot Trajectory Optimization. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 282–289.
[37]
Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh arrangements for solid geometry. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–15.
