More Web Proxy on the site http://driver.im/

article

Reducing the Complexity of Robot‘s Scene for Faster Collision Detection

Authors:

A. C. Nearchou,

N. A. Aspragathos,

D. P. SofotassiosAuthors Info & Claims

Journal of Intelligent and Robotic Systems, Volume 26, Issue 1

Pages 79 - 89

https://doi.org/10.1023/A:1008190406456

Published: 01 September 1999 Publication History

Abstract

In many real-life industrial applications such as welding and painting, the hand tip of a robot manipulator must follow a desired Cartesian curve while its body avoids collisions with obstacles in its environment. Collision detection is an absolutely essential task for any robotic manipulators in order to operate safely and effectively in cluttered environments. A significant factor that influences the complexity of the collision detection problem is the obstacles‘ density, i.e., the total number of obstacles in the robot‘s environment.

In this paper, a heuristic algorithm for approximating the collision detection problem into a simpler one is presented. The algorithm reduces the number of obstacles that must be examined during the robot‘s motion by applying efficient techniques from computational geometry. The algorithm runs in time O(max(n ^2 log m, n m)), and uses O(n ^2 + m n) space; with n being the number of obstacles in the robot‘s workspace, and m the total number of obstacles‘ vertices. Both costs are worst-case bounds.

References

[1]

1. Aho, A., Hopcroft, J. and Ullman, J.: Data Structures and Algorithms , Addison-Wesley, Reading, MA, 1983.

Digital Library

[2]

2. Brooks, R. A.: Solving the find-path problem by good representation of free space, IEEE Trans. Systems Man Cybernet. 13 (3) (1983), 190-197.

[3]

3. Chin, F. and Wang, C.: Optimal algorithms for the intersection and the minimum distance problems between planar polygons, IEEE Trans. Comput. 32 (12) (1983), 1203-1207.

Digital Library

[4]

4. Driscoll, J., Gabow, H., Shrairman, R. and Tarjan, R.: Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation, Comm. ACM 31 (11) (1988), 1343-1354.

Digital Library

[5]

5. Fredman, M. and Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM 34 (3) (1984), 538-544.

Digital Library

[6]

6. Gilbert, E. G. and Jonson, D. W.: Distance functions and their application to robot path planning in the presence of obstacles, IEEE J. Robot. Automat. 1 (1985), 21-30.

[7]

7. Hiller, M., Kecskemethy, A., Schmitz, T. and Schneider, M.: Modeling and simulation of mobile robots and large manipulators, in: 3rd Internat. Workshop on Advances in Robot Kinematics , Ferrara, Italy, September 7-9, 1992.

[8]

8. Hopcroft, J. E. and Krafft, D. B.: The challenge of robotics for computer science, in: J. T. Schwartz and C. K. Yap (eds), Advances in Robotics, Vol. 1: Algorithmic and Geometric Aspects of Robotics , Lawrence Erlbaum, Hillsdate, New Jersey, 1987, pp. 7-42.

[9]

9. Hurteau, G. and Stewart, N. F.: Distance calculation for imminent collision indication in a robot system simulation, Robotica 6 (1988), 47-51.

[10]

10. Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots, Internat. J. Robot. Res. 5 (1) (1986), 90-98.

Digital Library

[11]

11. Latombe, J.-C.: Robot Motion Planning , Kluwer Academic Publishers, Dordrecht, 1991.

Digital Library

[12]

12. Lozano Perez, T. and Wesley, M. A.: An algorithm for planning collision-free paths among polyhedral obstacles, Comm. ACM 22 (10) (1979), 560-570.

Digital Library

[13]

13. Lozano Perez, T.: Spatial planning: A configuration space approach, IEEE Trans. Comput. 32 (2) (1983), 108-120.

Digital Library

[14]

14. Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching , EATCS Monographs on Theoretical Computer Science, Springer, Berlin, 1984.

[15]

15. Nakamura, Y., Hanafusa, H. and Yoshikawa, T.: Task-priority based redunndancy control of robot manipulators, Internat. J. Robot. Res. 6 (1987), 3-17.

Digital Library

[16]

16. Nearchou, A. C. and Aspragathos, N. A.: Collision-free continuous path control of manipulators using genetic algorithms, J. Systems Engrg. 6 (1996), 20-32.

[17]

17. Nearchou, A. C. and Aspragathos, N. A.: A collision-detection scheme based on convex-hulls concept for generating kinematically feasible robot trajectories, in: 4th Internat. Workshop on Advances in Robot Kinematics , Slovenia, July 1994.

[18]

18. Tarjan, R.: Data Structures and Network Algorithms , Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.

Digital Library

[19]

19. Yao, F.: Computational geometry, in: J. van Leeuwen (ed.), The Handbook of Theoretical Computer Science , Elsevier Science Publishers, 1990.

Digital Library

[20]

20. Yap, C. K.: Algorithmic motion planning, in: J. T. Schwartz and C. K. Yap (eds), Algorithmic and Geometric Aspects of Robotics , Lawrence Erlbaum Associates, Hillsdate, New Jersey, 1987, pp. 95-143.

Cited By

Chen JLiu JLee W(2019)A Recursive Algorithm for On-line Clustering Obstacles Cluttered in Dynamic EnvironmentsJournal of Intelligent and Robotic Systems10.1023/A:101465500766833:2(209-230)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1023/A%3A1014655007668
Bendjilali KBelkhouche F(2018)Collision course by transformation of coordinates and plane decompositionRobotica10.5555/1552116.155211827:4(499-509)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.5555/1552116.1552118

Reducing the Complexity of Robot‘s Scene for Faster Collision Detection

Recommendations

Biomimetic application of desert ant visual navigation for mobile robot docking with weighted landmarks

Previous work has shown that honeybees use a snapshot model to determine a local vector to find their way home. A simpler, average landmark vector model has since been proposed for biologically-inspired mobile robot homing. Previously, the authors have ...
Collision-Detection for RoboCup@Work-Competitions
RoboCup 2017: Robot World Cup XXI
Abstract
The RobotCup@Work league is motivated by industrial scenarios where objects has to be automatically transported between different working positions. During these operations the rules prohibit and penalize collisions of robots with the arena. Human ...
Collision-free trajectory generation on assistive robot Neptune
PETRA '12: Proceedings of the 5th International Conference on PErvasive Technologies Related to Assistive Environments

This work demonstrates the integration of existing open source robotics tools to develop a collision free trajectory generation system for assistive environments and evaluates its performance. Trajectory generation and obstacle avoidance abilities were ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Intelligent and Robotic Systems

Journal of Intelligent and Robotic Systems Volume 26, Issue 1

September 1999

97 pages

ISSN:0921-0296

Issue’s Table of Contents

Copyright © Copyright © 1999 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 1999

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen JLiu JLee W(2019)A Recursive Algorithm for On-line Clustering Obstacles Cluttered in Dynamic EnvironmentsJournal of Intelligent and Robotic Systems10.1023/A:101465500766833:2(209-230)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1023/A%3A1014655007668
Bendjilali KBelkhouche F(2018)Collision course by transformation of coordinates and plane decompositionRobotica10.5555/1552116.155211827:4(499-509)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.5555/1552116.1552118

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents