×

Application of the laminar Navier-Stokes equations for solving 2D and 3D pathfinding problems with static and dynamic spatial constraints: implementation and validation in Comsol Multiphysics. (English) Zbl 1395.65144

In this fairly laborious paper the author is concerned with the numerical determination of one path or even with the optimal shortest path between two points in the space. He carries out his study in three steps. First, he uses some of CFD methods for the resolution of pathfinding problems that include: incomplete information of the spatial domain, dynamical evolution of the environment, one-way routes, and 3D environments for ground or nonholonomic flying vehicles. Then, in the second step he employs the Comsol Multiphysics 5.0 environment coupled with Matlab programming environment in order to implement and validate the proposed algorithms. Thirdly, he performs a sensitivity analysis of the proposed algorithms, i.e., the dependence of solutions on some key parameters. He is also interested in studying the dependence of solutions upon the changes in the geometry of domain.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
35Q30 Navier-Stokes equations
76D05 Navier-Stokes equations for incompressible viscous fluids
93B35 Sensitivity (robustness)
76M10 Finite element methods applied to problems in fluid mechanics

Software:

Theta*; BPA; COMSOL; Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amutha, B., Ponnavaikko, M.: Location update accuracy in human tracking system using zigbee modules. Int. J. Comput. Sci. Inf. Secur. 6(2), 322-331 (2009)
[2] Arvo, J., Kirk, D.: Fast ray tracing by ray classification. SIGGRAPH Comput. Graph. 21(4), 55-64 (1987) · doi:10.1145/37402.37409
[3] Batchelor G (2000) An Introduction to Fluid Dynamics. Cambridge University Press, Cambridge. doi:10.1017/CBO9780511800955(Cambridge Books Online)
[4] Bathe, K.: Computational Fluid and Solid Mechanics. Elsevier Science (2001). https://books.google.es/books?id=Id06Z4YMJLMC · Zbl 0985.74004
[5] Bretti, G., Natalini, R.: Piccoli B (2007) A fluid-dynamic traffic model on road networks. Arch. Comput. Methods Eng. 14(2), 139-172 (2007). doi:10.1007/s11831-007-9004-8 · Zbl 1127.76004 · doi:10.1007/s11831-007-9004-8
[6] Burns, EA; Hatem, M.; Leighton, MJ; Ruml, W.; Borrajo, D. (ed.); Felner, A. (ed.); Korf, RE (ed.); Likhachev, M. (ed.); Lpez, CL (ed.); Ruml, W. (ed.); Sturtevant, NR (ed.), Implementing fast heuristic search code (2012), Palo Alto
[7] Calvo, C., Villacorta-Atienza, J., Mironov, V., Gallego, V., Makarov, V.: Waves in isotropic totalistic cellular automata: application to real-time robot navigation. Adv. Complex Syst. 19(4), 1650012-1650018 (2016). doi:10.1142/S0219525916500120 · doi:10.1142/S0219525916500120
[8] Choset, H., Lynch, K., Hutchinson, S., Kantor, G., Lydia, W., Kavraki, E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementation. Intelligent Robotics and Autonomous Agents series. MIT Press, Cambridge (2005) · Zbl 1081.68700
[9] Chrpa, L., Novak, P.: Dynamic Trajectory Replanning for Unmanned Aircrafts Supporting Tactical Missions in Urban Environments. Holonic and Multi-Agent Systems for Manufacturing. Springer, Berlin (2011)
[10] Ciarlet, P., Lions, J.: Handbook of Numerical Analysis: Numerical methods for fluids (pt. 3). Handbook of Numerical Analysis. North-Holland (1990). https://books.google.es/books?id=S0Hqp3vOVxkC · Zbl 1180.35526
[11] Connolly, C., Burns, J., Weiss, R.: Path planning using laplace’s equation. In: 1990 IEEE International Conference on Robotics and Automation, 1990. Proceedings, vol. 3, pp. 2102-2106 (1990)
[12] Connor, D.: Integrating Planning and Control for Constrained Dynamical Systems. PhD., University of Pennsylvania (2007) · Zbl 0962.93068
[13] Daniel, K., Nash, A., Koenig, S., Felner, A.: Theta*: any-angle path planning on grids. J. Artif. Intell. Res. 39, 533-579 (2010) · Zbl 1205.68373
[14] Dean, W.: Lxxii. the stream-line motion of fluid in a curved pipe (second paper). Lond Edinb. Dublin Philos. Mag. J. Sci. 5(30), 673-695 (1928). doi:10.1080/14786440408564513 · doi:10.1080/14786440408564513
[15] Dickmann, D.: On the Near Field Mean Flow Structure of Transverse Jets Issuing Into a Supersonic Freestream. University of Texas at Arlington (2007). https://books.google.es/books?id=4ee-g96_F5gC · Zbl 0863.76016
[16] Dijkstra, E.: A Short Introduction to the Art of Programming. Techn. Hogeschool, Eindhoven (1971)
[17] Eberly, D.: 3D Game Engine Design: A Practical Approach to Real-Time Computer Graphics. CRC Press, Boca Raton (2006)
[18] Fay, J.: Introduction to Fluid Mechanics. MIT Press (1994). https://books.google.es/books?id=XGVpue4954wC · Zbl 0900.76001
[19] Fuerstman, M., Deschatelets, P., Kane, R., Schwartz, A., Kenis, P., Deutch, J., Whitesides, G.: Solving mazes using microfluidic networks. Langmuir 19(11), 4714-4722 (2003). doi:10.1021/la030054x · doi:10.1021/la030054x
[20] Girod, B., Greiner, G., Niemann, H.: Principles of 3D Image Analysis and Synthesis. The Springer International Series in Engineering and Computer Science. Springer, US (2013). https://books.google.es/books?id=jVHuBwAAQBAJ · Zbl 0466.76011
[21] Glowinski, R., Neittaanmäki, P.: Partial Differential Equations: Modelling and Numerical Simulation. Computational Methods in Applied Sciences. Springer, Netherlands (2008). https://books.google.es/books?id=xKhfyc0Nf54C · Zbl 1140.65007
[22] Hertzog, D., Ivorra, B., Mohammadi, B., Bakajin, O., Santiago, J.: Optimization of a microfluidic mixer for studying protein folding kinetics. Anal. Chem. 78(13), 4299-4306 (2006). doi:10.1021/ac051903j · doi:10.1021/ac051903j
[23] Heywood, J.G., Rannacher, R., Turek, S.: Artificial boundaries and flux and pressure conditions for the incompressible navierstokes equations. Int. J. Numer. Methods Fluids 22(5), 325-352 (1996) · Zbl 0863.76016 · doi:10.1002/(SICI)1097-0363(19960315)22:5<325::AID-FLD307>3.0.CO;2-Y
[24] Hunt, B., Lipsman, R., Rosenberg, J.: A Guide to MATLAB: For Beginners and Experienced Users. Cambridge University Press (2001). https://books.google.es/books?id=XhQBx9LJKIAC · Zbl 0983.68255
[25] Hysing, J., Turek, S.: Evaluation of commercial and academic cfd codes for a two-phase flow benchmark test case. Int. J. Comput. Sci. Eng. 10(4), 387-394 (2015) · doi:10.1504/IJCSE.2015.070993
[26] Infante, J.A., Ivorra, B., Ramos, A., Rey, J.: On the modelling and simulation of high pressure processes and inactivation of enzymes in food engineering. Math. Models Methods Appl. Sci. 19(12), 2203-2229 (2009). doi:10.1142/S0218202509004091 · Zbl 1180.35526 · doi:10.1142/S0218202509004091
[27] Isebe, D., Azerad, P., Bouchette, F., Ivorra, B.: Mohammadi B (2008) Shape optimization of geotextile tubes for sandy beach protection. Int. J. Numer. Methods Eng. 74(8), 1262-1277 (2008). doi:10.1002/nme.2209 · Zbl 1159.74394 · doi:10.1002/nme.2209
[28] Ivorra, B., Hertzog, D., Mohammadi, B., Santiago, J.: Semi-deterministic and genetic algorithms for global optimization of microfluidic protein-folding devices. Int. J. Numer. Methods Eng. 66(2), 19-333 (2006). doi:10.1002/nme.1562 · Zbl 1110.76311 · doi:10.1002/nme.1562
[29] Ivorra, B., Redondo, J., Santiago, J., Ortigosa, P., Ramos, A.: Two- and three-dimensional modeling and optimization applied to the design of a fast hydrodynamic focusing microfluidic mixer for protein folding. Phys. Fluids 25(3), 032001 (2013). doi:10.1063/1.4793612 · Zbl 1315.76047 · doi:10.1063/1.4793612
[30] Johnson, R.: Handbook of Fluid Dynamics. Handbook Series for Mechanical Engineering. Taylor & Francis, Oxfordshire (1998)
[31] Katevas, N.: Mobile Robotics in Healthcare. Assistive technology research series. IOS Press (2001). https://books.google.es/books?id=jT__IKy9wTgC
[32] Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. 5(1), 90-98 (1986) · doi:10.1177/027836498600500106
[33] Koenig, S., Likhachev, M.: D*lite. In: Eighteenth National Conference on Artificial Intelligence, pp. 476-483. American Association for Artificial Intelligence (2002)
[34] Kwon, H.J.: Use of comsol simulation for undergraduate fluid dynamics course. In: 2012 ASEE Annual Conference & Exposition, San Antonio, Texas. https://peer.asee.org/22167 (2012)
[35] Lee, V., Law, M., Wee, S.: Theory to practice on finite element method and computational fluid dynamics tools. Aust. J. Eng. Educ. 22(2), 123-133 (2015)
[36] Lolla, S.: Path Planning in Time Dependent Flows using Level Set Methods. PhD., University of Massachusetts Institute Of Technology (2012) · Zbl 1414.91314
[37] Louste, C., Liegeois, A.: Near optimal robust path planning for mobile robots: the viscous fluid method with friction. J. Intell. Robot. Syst. 27(1), 99-112 (2000) · Zbl 0962.93068 · doi:10.1023/A:1008102230551
[38] Nau, D., Kumar, V., Kanal, L.: General branch and bound, and its relation to A* and AO*. Artif. Intell. 23(1), 29-58 (1984) · Zbl 0537.68064 · doi:10.1016/0004-3702(84)90004-3
[39] Pepper, D., Wang, X.: Benchmarking COMSOL Multiphysics 3.5a CFD problems. In: Proceeding of the Cosmol Conference 2009, Boston. Comsol Inc. (2009)
[40] Pimenta, L., Michael, N., Mesquita, R., Pereira, G., Kumar, V.: Control of swarms based on hydrodynamic models. In: IEEE International Conference on Robotics and Automation, 2008. ICRA 2008, pp. 1948-1953 (2008)
[41] Premakumar, P.: A* (A star) search for path planning tutorial. Matlab Central. http://www.mathworks.com/matlabcentral/mlc-downloads/downloads/submissions/26248/versions/3/download/zip (2010)
[42] Ramos Del Olmo, A.: Introducción al análisis matemático del método de elementos finitos. Editorial Complutense, Madrid (2013). ISBN:978-8499381282 · Zbl 1127.76004
[43] Rimon, E., Koditschek, D.: Exact robot navigation using artificial potential functions. IEEE Trans. Robot. Autom. 8(5), 501-518 (1992) · doi:10.1109/70.163777
[44] Roussos, G., Dimarogonas, D.V., Kyriakopoulos, K.J.: 3d navigation and collision avoidance for nonholonomic aircraft-like vehicles. Int. J. Adapt. Control Signal Process. 24(10), 900-920 (2010). doi:10.1002/acs.1199 · Zbl 1202.90077 · doi:10.1002/acs.1199
[45] Sun, X., Yeoh, W., Uras, T., Koenig, S.: Incremental ara*: an incremental anytime search algorithm for moving-target search. In: International Conference on Automated Planning and Scheduling (2012)
[46] Suzuno, K., Ueyama, D., Branicki, M., Tth, R., Braun, A., Lagzi, I.: Maze solving using fatty acid chemistry. Langmuir 30(31), 9251-9255 (2014). doi:10.1021/la5018467 · doi:10.1021/la5018467
[47] Szab, C., Sobota, B.: Path-finding algorithm application for route-searching in different areas of computer graphics. In: Zhang, Y. (ed.) New Frontiers in Graph Theory. InTech (2012). ISBN:978-953-51-0115-4 · Zbl 1414.91314
[48] Tabatabaian, M.: Comsol 5 for Engineers. Multiphysics Modeling Series. Mercury Learning & Information (2015). https://books.google.es/books?id=twhSrgEACAAJ
[49] Twizell, E., Bright, N.: Numerical modelling of fan performance. Appl. Math. Model. 5(4), 246-250 (1981). doi:10.1016/S0307-904X(81)80074-1 · Zbl 0466.76011 · doi:10.1016/S0307-904X(81)80074-1
[50] Villacorta-Atienza, J., Calvo, C., Makarov, V.: Prediction-for-compaction: navigation in social environments using generalized cognitive maps. Biol. Cybern. 109(3), 307-320 (2015). doi:10.1007/s00422-015-0644-8 · Zbl 1414.91314 · doi:10.1007/s00422-015-0644-8
[51] Wang, J., Deng, W.: Optimizing capacity of signalized road network with reversible lanes. Transport (2015). doi:10.3846/16484142.2014.994227 · Zbl 1315.76047
[52] Wu, X., Zhang, S.: The study and application of artificial intelligence pathfinding algorithm in game domain. In: 2011 International Conference on Computer Science and Service System (CSSS), pp. 3772-3774. IEEE (2011). doi:10.1109/CSSS.2011.5974547
[53] Zeng, W., Church, R.L.: Finding shortest paths on real road networks: the case for A*. Int. J. Geogr. Inf. Sci. 23(4), 531-543 (2009). doi:10.1080/13658810801949850 · doi:10.1080/13658810801949850
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.