Abstract:
An algorithm for computing the Euclidean distance between a pair of convex sets in R/sup m/ is described. Extensive numerical experience with a broad family of polytopes ...Show MoreMetadata
Abstract:
An algorithm for computing the Euclidean distance between a pair of convex sets in R/sup m/ is described. Extensive numerical experience with a broad family of polytopes in R/sup 3/ shows that the computational cost is approximately linear in the total number of vertices specifying the two polytopes. The algorithm has special features which makes its application in a variety of robotics problems attractive. These features are discussed and an example of collision detection is given.<>
Published in: IEEE Journal on Robotics and Automation ( Volume: 4, Issue: 2, April 1988)
DOI: 10.1109/56.2083
Citations are not available for this document.
Cites in Papers - |
Cites in Papers - IEEE (423)
Select All
1.
Wen Yang, Wanxin Jin, "ContactSDF: Signed Distance Functions as Multi-Contact Models for Dexterous Manipulation", IEEE Robotics and Automation Letters, vol.10, no.5, pp.4212-4219, 2025.
2.
Rilun Xia, Dongming Wang, Chenqi Mou, "Collision Detection Between Convex Objects Using Pseudodistance and Unconstrained Optimization", IEEE Transactions on Robotics, vol.41, pp.253-268, 2025.
3.
Jiayu Fan, Nikolce Murgovski, Jun Liang, "Efficient Collision Avoidance for Autonomous Vehicles in Polygonal Domains", IEEE Transactions on Transportation Electrification, vol.11, no.2, pp.5396-5406, 2025.
4.
Dongqi Wang, Jiyu Yu, Shuangpeng Wu, Zhang Li, Chao Li, Rong Xiong, Shaoxing Qu, Yue Wang, "A Hierarchical MPC for End-Effector Tracking Control of Legged Mobile Manipulators", IEEE Transactions on Automation Science and Engineering, vol.22, pp.4855-4866, 2025.
5.
Lifeng Wang, Yongde Zhang, Cunli Guo, "Path Planning for a Prostate Intervention Robot Based on an Improved Bi-RRT Algorithm", IEEE/ASME Transactions on Mechatronics, vol.30, no.1, pp.668-678, 2025.
6.
Takanori Jin, Taisuke Kobayashi, Masahiro Doi, "Real-time Detailed Self-collision Avoidance in Whole-body Model Predictive Control", 2024 IEEE-RAS 23rd International Conference on Humanoid Robots (Humanoids), pp.675-681, 2024.
7.
Yuda Chen, Haoze Dong, Zhongkui Li, "Asynchronous Spatial-Temporal Allocation for Trajectory Planning of Heterogeneous Multi-Agent Systems", 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp.8504-8509, 2024.
8.
Noriaki Takasugi, Masaya Kinoshita, Yasuhisa Kamikawa, Ryoichi Tsuzaki, Atsushi Sakamoto, Toshimitsu Kai, Yasunori Kawanami, "Real-time Perceptive Motion Control using Control Barrier Functions with Analytical Smoothing for Six-Wheeled-Telescopic-Legged Robot Tachyon 3", 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp.6802-6809, 2024.
9.
Wei Gao, "Efficient Incremental Penetration Depth Estimation between Convex Geometries", 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp.5444-5451, 2024.
10.
Yunze Hu, Xuru Yang, Kangjie Zhou, Qinghang Liu, Kang Ding, Han Gao, Pingping Zhu, Chang Liu, "SwarmPRM: Probabilistic Roadmap Motion Planning for Large-Scale Swarm Robotic Systems", 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp.10222-10228, 2024.
11.
Xuru Yang, Yunze Hu, Han Gao, Kang Ding, Zhaoyang Li, Pingping Zhu, Ying Sun, Chang Liu, "Risk-Aware Non-Myopic Motion Planner for Large-Scale Robotic Swarm Using CVaR Constraints", 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp.5784-5790, 2024.
12.
Seoki An, Somang Lee, Jeongmin Lee, Sunkyung Park, Dongjun Lee, "Collision Detection between Smooth Convex Bodies via Riemannian Optimization Framework", 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp.12464-12471, 2024.
13.
Lorenzo Paiola, Giorgio Grioli, Antonio Bicchi, "On the Evaluation of Collision Probability Along a Path", IEEE Transactions on Robotics, vol.40, pp.4449-4468, 2024.
14.
Sarthak Arora, Karthik Subramanian, Odysseus Adamides, Ferat Sahin, "Using Multi-channel 3D Lidar for Safe Human-Robot Interaction", 2024 IEEE 20th International Conference on Automation Science and Engineering (CASE), pp.1823-1830, 2024.
15.
Zuan Li, Wenjing Zhang, Guopeng Wang, Senchun Yao, Yuchao Yan, Yuntao Li, "Structural Optimization and Control Strategy of Continuum Manipulator for Wrapping", 2024 43rd Chinese Control Conference (CCC), pp.4669-4674, 2024.
16.
Lihao Xu, Xiaogang Xiong, Yang Bai, "Dynamic Control Barrier Function Based Trajectory Planning for Mobile Manipulator", 2024 43rd Chinese Control Conference (CCC), pp.3815-3820, 2024.
17.
Shicheng Qiu, Yong Zhao, Zhengrong Li, Zhiyi Zhang, Shaojun Hu, "Physically-based Virtual Picking System for Hand-Fruit Interaction Using Data Gloves", 2024 10th International Conference on Virtual Reality (ICVR), pp.177-183, 2024.
18.
Quentin Le Lidec, Wilson Jallet, Louis Montaut, Ivan Laptev, Cordelia Schmid, Justin Carpentier, "Contact Models in Robotics: A Comparative Analysis", IEEE Transactions on Robotics, vol.40, pp.3716-3733, 2024.
19.
Han Gao, W. Pengying, S. Yao, Kangjie Zhou, M. Ji, Hangxin Liu, Chang Liu, "Probabilistic Visibility-Aware Trajectory Planning for Target Tracking in Cluttered Environments", 2024 American Control Conference (ACC), pp.594-600, 2024.
20.
Amirreza Fahim Golestaneh, Maxwell Hammond, Venanzio Cichella, "Scalable Optimal Motion Planning for Multi-Agent Systems by Cosserat Theory of Rods", IEEE Control Systems Letters, vol.8, pp.1391-1396, 2024.
21.
Jihao Huang, Xuemin Chi, Zhitao Liu, Hongye Su, "Whole-body Dynamic Collision Avoidance with Time-varying Control Barrier Functions", 2024 36th Chinese Control and Decision Conference (CCDC), pp.5149-5154, 2024.
22.
Minjae Song, Yeseung Kim, Min Jun Kim, Daehyung Park, "Graph-based 3D Collision-distance Estimation Network with Probabilistic Graph Rewiring", 2024 IEEE International Conference on Robotics and Automation (ICRA), pp.10939-10945, 2024.
23.
Kallol Saha, Vishal Mandadi, Jayaram Reddy, Ajit Srikanth, Aditya Agarwal, Bipasha Sen, Arun Singh, Madhava Krishna, "EDMP: Ensemble-of-costs-guided Diffusion for Motion Planning", 2024 IEEE International Conference on Robotics and Automation (ICRA), pp.10351-10358, 2024.
24.
Max Asselmeier, Jane Ivanova, Ziyi Zhou, Patricio A. Vela, Ye Zhao, "Hierarchical Experience-informed Navigation for Multi-modal Quadrupedal Rebar Grid Traversal", 2024 IEEE International Conference on Robotics and Automation (ICRA), pp.8065-8072, 2024.
25.
Peter Werner, Alexandre Amice, Tobia Marcucci, Daniela Rus, Russ Tedrake, "Approximating Robot Configuration Spaces with few Convex Sets using Clique Covers of Visibility Graphs", 2024 IEEE International Conference on Robotics and Automation (ICRA), pp.10359-10365, 2024.
26.
Muhammad Alhaddad, Konstantin Mironov, Aleksey Staroverov, Aleksandr Panov, "Neural Potential Field for Obstacle-Aware Local Motion Planning", 2024 IEEE International Conference on Robotics and Automation (ICRA), pp.9313-9320, 2024.
27.
Xuda Ding, Han Wang, Yi Ren, Yu Zheng, Cailian Chen, Jianping He, "Online Control Barrier Function Construction for Safety-Critical Motion Control of Manipulators", IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol.54, no.8, pp.4761-4771, 2024.
28.
Chao Wei, Mo Lv, Benshan Ma, Zhe Zhang, Botong Zhao, Menglun Su, "Multi-Segment Polynomial Trajectory Generation of Autonomous Vehicles Based on Quadratic Programming", 2024 4th International Conference on Computer, Control and Robotics (ICCCR), pp.171-177, 2024.
29.
Maxwell Hammond, Venanzio Cichella, Amirreza F Golestaneh, Caterina Lamuta, "Path Planning for Continuum Rods Using Bernstein Surfaces", 2024 IEEE 7th International Conference on Soft Robotics (RoboSoft), pp.109-114, 2024.
30.
Louis Montaut, Quentin Le Lidec, Vladimir Petrik, Josef Sivic, Justin Carpentier, "GJK++: Leveraging Acceleration Methods for Faster Collision Detection", IEEE Transactions on Robotics, vol.40, pp.2564-2581, 2024.
Cites in Papers - Other Publishers (570)
1.
S. Sheshanarayana, C.G. Armstrong, A. Murphy, T.T. Robinson, N.L. Iorga, J.R. Barron, "Efficient methods to build structural performance envelopes in characteristic load space", Computers & Structures, vol.306, pp.107595, 2025.
2.
Kaishu Liu, Jijun Gu, Xiaoyong He, Long Zhang, "Optimization algorithms for dynamic environmental sensing and motion planning of quadruped robots in complex environments on unmanned offshore platforms", Measurement Science and Technology, vol.36, no.1, pp.015122, 2025.
3.
Aleksandr Panov, Aleksey Logunov, Muhammad Alhaddad, Konstantin Mironov, Konstantin Yakovlev, , 2024.
4.
Jiakang Zhou, Yue Cao, Yu-Xuan Ren, Steve Feng Shu, "SPADE: A spatial information assisted collision distance estimator for robotic arm", Journal of Automation and Intelligence, 2024.
5.
V. A. Alexandrov, E. P. Volokitin, "An\\xa0Embedded Flexible Polyhedron with Nonconstant Dihedral Angles", Siberian Mathematical Journal, vol.65, no.6, pp.1259, 2024.
6.
Mehran Ghafarian Tamizi, Homayoun Honari, Aleksey Nozdryn-Plotnicki, Homayoun Najjaran, "End-to-end deep learning-based framework for path planning and collision checking: bin-picking application", Robotica, pp.1, 2024.
7.
Aman Mittal, Narasimha Mangadoddy, Raja Banerjee, "GPU based discrete element modeling for convex polyhedral shape particles: Development and validation", Powder Technology, pp.120407, 2024.
8.
Hikaru Yamamoto, Masaki Abe, Taichi Watanabe, "A Research on Improvement of Accuracy of Collision Detection for Rotaion Rigid Bodies In Real-Time Graphics", The Journal of the Society for Art and Science, vol.23, no.3, pp.7_1, 2024.
9.
Diana C. de Oliveira, Hani Cheikh Sleiman, Kelly Payette, Jana Hutter, Lisa Story, Joseph V. Hajnal, Daniel C. Alexander, Rebecca J. Shipley, Paddy J. Slator, "A flexible generative algorithm for growing in silico placentas", PLOS Computational Biology, vol.20, no.10, pp.e1012470, 2024.
10.
Pengju Yang, Feng Shen, Dingjie Xu, Ronghai Liu, "A fast collision detection method based on point clouds and stretched primitives for manipulator obstacle-avoidance motion planning", International Journal of Advanced Robotic Systems, vol.21, no.5, 2024.
11.
Eduardo Anitua, Asier Lazcano, Asier Eguia, Mohammad Hamdan Alkhraisat, "Assessing the Impact of IOS Scanning Accuracy on Additively Manufactured Occlusal Splints", Dentistry Journal, vol.12, no.10, pp.298, 2024.
12.
Yusheng Yang, Jiajia Liu, Hongpeng Zhou, Afimbo Reuben Kwabena, Yuqiao Zhong, Yangmin Xie, "RobotSDF: Implicit Morphology Modeling for the Robotic Arm", Sensors, vol.24, no.16, pp.5248, 2024.
13.
Ariana Brenner Clerkin, Nicole Pagane, Devany W. West, Andrew J. Spakowitz, Viviana I. Risca, , 2024.
14.
Qiubing Zhuang, Zhonggui Chen, Keyu He, Juan Cao, Wenping Wang, "Dynamics simulation-based packing of irregular 3D objects", Computers & Graphics, pp.103996, 2024.
15.
Amir Trabelsi, Juan Sandoval, Abdelfattah Mlika, Samir Lahouar, Said Zeghloul, Med Amine Laribi, "Robot base placement and tool mounting optimization based on capability map for robot-assistant camera holder", Robotica, pp.1, 2024.
16.
Xi Wang, Wei Wu, Hehua Zhu, "Meta-contact analysis based on contact theory in three-dimensional discontinuous deformation analysis", IOP Conference Series: Earth and Environmental Science, vol.1331, no.1, pp.012014, 2024.
17.
Ryan Kim, Paul M. Torrens, "Boundary SPH for Robust Particle–Mesh Interaction in Three Dimensions", Algorithms, vol.17, no.5, pp.218, 2024.
18.
Daeyong Yang, Eui Jung, , 2024.
19.
Xiaofeng Zhang, Bo Tao, Du Jiang, Baojia Chen, Dalai Tang, Xin Liu, "Novel Probabilistic Collision Detection for Manipulator Motion Planning Using HNSW", Machines, vol.12, no.5, pp.321, 2024.
20.
Andong Liu, Yawen Zhang, Jiayun Fu, Yuankun Yan, Wen-An Zhang, "3D-AMM: a 3D artificial moment method for path planning of manipulator in multiple obstacles scenario", Industrial Robot: the international journal of robotics research and application, 2024.
21.
Pengfei Liu, Yuqing Zhang, He Wang, Milo K. Yip, Elvis S. Liu, Xiaogang Jin, "Real-time Collision Detection between General SDFs", Computer Aided Geometric Design, pp.102305, 2024.
22.
Thi Vo, "Theory and simulation of ligand functionalized nanoparticles – a pedagogical overview", Soft Matter, 2024.
23.
Vladimir V. SEMENOV, Nataliia LYASHKO, Stanislav ZUB, Yevhen HAVRYLKO, "Finding a Nearest Pair of Points Between Two Smooth Curves in Euclidean Space", Computational Methods and Mathematical Modeling in Cyberphysics and Engineering Applications 1, pp.367, 2024.
24.
Christopher Douglas, Jae Sung Huh, Sang Ook Jun, Il Yong Kim, "Packing optimization of practical systems using a dynamic acceleration methodology", Journal of Engineering and Applied Science, vol.71, no.1, 2024.
25.
S. Bousigues, L. Gajny, W. Skalli, X. Ohl, P. Tétreault, N. Hagemeister, "Evaluation of a method to quantify posture and scapula position using biplanar radiography", Medical Engineering & Physics, pp.104167, 2024.
26.
Xin Wei, Yiren Sun, Hongren Gong, Yuhua Li, Jingyun Chen, "3D identification and characterization of force chains in asphalt concrete based on continuum mesomechanics", Computers & Structures, vol.297, pp.107329, 2024.
27.
Weijian Liang, Kai-Yuan He, Yin-Fu Jin, Zhen-Yu Yin, "A gradient-smoothed material point method for reducing cell crossing noise in large deformation problems", Computers and Geotechnics, vol.169, pp.106169, 2024.
28.
Rui Lu, Qiang Luo, Tengfei Wang, David P. Connolly, Tao Xie, "A combined experimental and DEM investigation of grain interlocking in sheared granular assemblies", Particuology, 2024.
29.
Pedro López-Adeva Fernández-Layos, Luis F.S. Merchante, "Convex Body Collision Detection using the Signed Distance Function", Computer-Aided Design, pp.103685, 2024.
30.
Borui Yang, Guiyong Zhang, Honghua Rao, Shushan Wang, Biye Yang, Zhe Sun, "Numerical simulation of the maneuvering performance of ships in broken ice area", Ocean Engineering, vol.294, pp.116783, 2024.
