Grid Based and Random Based Ant Colony Algorithms for Automatic Hose Routing in 3D Space

Authors: Gishantha Thantulage, Tatiana Kalganova, Manissa Wilson

Abstract:

Ant Colony Algorithms have been applied to difficult combinatorial optimization problems such as the travelling salesman problem and the quadratic assignment problem. In this paper gridbased and random-based ant colony algorithms are proposed for automatic 3D hose routing and their pros and cons are discussed. The algorithm uses the tessellated format for the obstacles and the generated hoses in order to detect collisions. The representation of obstacles and hoses in the tessellated format greatly helps the algorithm towards handling free-form objects and speeds up computation. The performance of algorithm has been tested on a number of 3D models.

Keywords: Ant colony algorithm, Automatic hose routing, tessellated format, RAPID.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329450

References:

[1] Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26, No. 1, pp. 1-13.
[2] Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). From natural to artificial swarm intelligence. New York: Oxford University Press.
[3] Corne, D. Dorigo, M., & Glover, F. (Eds.). (1999). New ideas in optimization. Maidnhead, UK: McGraw-Hill.
[4] Gambardella, L.M., & Dorigo, M. (1996). Solving symmetric and Asymmetric TSPs by ant colonies. Proceedings of IEEE International Conference. pp. 622-627.
[5] Gambardella, L.M., & Dorigo, M. (1997). Ant Colony System: A cooperative learning approach to the travelling salesman problem. Evolutionary Computation, IEEE Transactions. pp. 53-66.
[6] Gambardella, L.M., & Dorigo, M. (1999). Ant algorithms for discrete optimization. Artificial Life 5: Massachusetts Institute of Technology. pp. 137-172.
[7] Sandurkar, S., & Chen, W. (1998). GAPRUS - Genetic algorithms based pipe routing using tessellated objects. The journal of computers in industry.
[8] Gottschalk, S., Lin, M.C., & Manocha, D. RAPID (Robust and Accurate Polygon Interface Detection). Available: http://www.cs.unc.edu/~geom/OBB/OBBT.html