A pathfinding module for the indoor navigation system NaviSecure

• Autorzy: Nazarczuk Maciej , Niewiadomski Artur
• Języki publikacji: EN

Abstrakty

EN

NaviSecure is an indoor navigation system developed atUniversity of Siedlce. It utilizes a dedicated hierarchical building map and an infrastructure of Bluetooth Low Energy transmitters, as well as hazard detectors such as smoke, flood, and gas sensors. The system facilitates daily navigation and provides emergency assistance while addressing the needs of individuals with disabilities. In this paper we present the pathfinding module of the NaviSecure system, implemented on top of the Neo4j graph database. We introduce the basic concepts behind our approach, we discuss the system architecture and our custom approach to deal with special needs of the users. Finally, we show the results of our experimental evaluation of several graph algorithms, modified to meet NaviSecure’s specific requirements. The results confirm the efficiency of our approach.

Słowa kluczowe

EN

indoor navigation; pathfinding; accessibility; Dijkstra algorithm; A* algorithm; graph database; Neo4J

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2024
• Tom: vol. 2 (31)
• Strony: 123--137
• Opis fizyczny: Bibliogr. 47 poz., rys., tab., wykr.

Twórcy

autor

Nazarczuk Maciej

• University of Siedlce, Faculty of Exact and Natural Sciences, Institute of Computer Science, ul. 3 Maja 54, 08-110 Siedlce, Poland

• https://orcid.org/0009-0008-6559-7000

autor

Niewiadomski Artur

• University of Siedlce, Faculty of Exact and Natural Sciences, Institute of Computer Science, ul. 3 Maja 54, 08-110 Siedlce, Poland

• https://orcid.org/0000-0002-9652-5092

Bibliografia

• 1. Extending Neo4j. https://neo4j.com/docs/java-reference/current/extending-neo4j/, [Accessed 19-07-2023].
• 2. Graph Data Science library repository.https://github.com/neo4j/graph-data-science/,[Accessed 19-07-2023].
• 3. Graph Hopper Routing Engine repository.https://github.com/graphhopper/graphhopper,[Accessed 10-07-2023].
• 4. Neo4j - cypher query language.https://neo4j.com/developer/cypher/, [Accessed 19-07-2023].
• 5. Open street map - about page.https://www.openstreetmap.org/about, [Accessed 12-07-2023].
• 6. Open JDK Code Tools: JMH.https://openjdk.org/projects/code-tools/jmh/, [Accessed12-07-2023].
• 7. Ahmetovic, D., Gleason, C., Ruan, C., Kitani, K., Takagi, H., Asakawa, C.: Navcog: A navigationalcognitive assistant for the blind. In: Proceedings of the 18th International Conference on Human-Computer Interaction with Mobile Devices and Services. p. 90-99. MobileHCI ’16, Associationfor Computing Machinery, New York, NY, USA 2016). https://doi.org/10.1145/2935334.2935361, https://doi.org/10.1145/2935334.2935361
• 8. Alqahtani, E., Alshamrani, F., Syed, H., Al-Haidari, F.: Survey on algorithms and techniques forindoor navigation systems pp. 1-9 (04 2018).https://doi.org/10.1109/NCG.2018.8593096
• 9. Anthapu, R.: Graph Data Processing with Cypher: A practical guide to building graph traversalqueries using the Cypher syntax on Neo4j. Packt Publishing (2022) ,https://books.google.pl/books?id=NR2gEAAAQBAJ
• 10. Barrett, C., Tinelli, C.: Satisfiability modulo theories. Handbook of model checking pp. 305-343(2018).
• 11. Biere, A., Heule, M., van Maaren, H.: Handbook of satisfiability, vol. 185. IOS press (2009).
• 12. Bondy, J.A., Murty, U.: Graph Theory With Applications. Elsevier Science Ltd/North-Holland, hardcover edn. (1984).
• 13. Bryant, R.E.: Binary decision diagrams. Handbook of model checking pp. 191-217 (2018).
• 14. Burdick, J.W.: Summary of the A* algorithm. http://robotics.caltech.edu/wiki/images/e/e0/Astar.pdf, [Accessed 12-07-2023].
• 15. Chandel, V., Ahmed, N., Arora, S., Ghose, A.: Inloc: An end-to-end robust indoor localization androuting solution using mobile phones and ble beacons. In: 2016 International Conference on IndoorPositioning and Indoor Navigation (IPIN). pp. 1-8 (2016). https://doi.org/10.1109/IPIN.2016.7743592.
• 16. Chen, L.W., Cheng, J.H., Tseng, Y.C.: Optimal path planning with spatial-temporal mobil-ity modeling for individual-based emergency guiding. vol. 45, pp. 1-1 (12 2015). https://doi.org/10.1109/TSMC.2015.2445875
• 17. Chen, L.W., Chung, J.J., Liu, J.X.: Gofast: A group-based emergency guiding system with dedicatedpath planning for mobile users using smartphones. In: 2015 IEEE 12th International Conference onMobile Ad Hoc and Sensor Systems. pp. 467-468 (2015). https://doi.org/10.1109/MASS.2015.35
• 18. Deng, K., Li, M., Zhong, W.: Optimal emergency evacuation route planning model based on fire pre-diction data. Mathematics10(2), 379-392 (2022).https://doi.org/10.3390/math10020379
• 19. Foead, D., Ghifari, A., Kusuma, M.B., Hanafiah, N., Gunawan, E.: A systematic literature review of A* pathfinding. Procedia Computer Science179, 507-514 (2021). https://doi.org/https://doi.org/10.1016/j.procs.2021.01.034, 5th International Conference on Computer Scienceand Computational Intelligence 2020.
• 20. Gao, J., Ye, W., Guo, J., Li, Z.: Deep reinforcement learning for indoor mobile robot path planning.Sensors20(19), 5493 (2020).https://doi.org/10.3390/s20195493, https://www.mdpi.com/1424-8220/20/19/5493
• 21. Gomes, C.P., Kautz, H., Sabharwal, A., Selman, B.: Satisfiability solvers. Foundations of ArtificialIntelligence3, 89-134 (2008).
• 22. Haklay, M., Weber, P.: Openstreetmap: User-generated street maps. IEEE Pervasive Computing7(4), 12-18 (2008). https://doi.org/10.1109/MPRV.2008.80
• 23. Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimumcost paths. IEEE Transactions on Systems Science and Cybernetics 4(2), 100-107 (1968). https://doi.org/10.1109/TSSC.1968.300136
• 24. Hodler, A.E., Needham, M.: Graph data science using Neo4j. In: Massive Graph Analytics, pp.433-457. Chapman and Hall/CRC (2022).
• 25. Jiang, J.R., Subakti, H., Liang, H.S.: Fingerprint Feature Extraction for Indoor Localization. Sensors21, 5434 (Aug 2021). https://doi.org/10.3390/s21165434
• 26. Ko, N.Y., Noh, S.W., Moon, Y.S.: Implementing indoor navigation of a mobile robot pp. 198-00 (2013). https://doi.org/10.1109/ICCAS.2013.6703892
• 27. Kumar, A., Singh, A.: Graph Database Modeling with Neo4j. Amazon Digital Services LLC - KDPPrint US (2020), https://books.google.pl/books?id=Z9PZzQEACAAJ
• 28. Laaber, C., Leitner, P.: An evaluation of open-source software microbenchmark suites for continuous performance assessment. In: Proceedings of the 15th International Conference on Mining Software Repositories. pp. 119-130 (2018).
• 29. Leitch, S.G., Ahmed, Q.Z., Abbas, W.B., Hafeez, M., Laziridis, P.I., Sureephong, P., Alade, T.: On indoor localization using wifi, ble, uwb, and imu technologies. Sensors23(20) (2023). https://doi.org/10.3390/s23208598
• 30. Li, Y., Shin, B.S.: Internal topology based flexible shortest path planning method for indoor navigation pp. 171-176 (2015).
• 31. Link, J.A.B., Smith, P., Viol, N., Wehrle, K.: Footpath: Accurate map-based indoor navigationusing smartphones. In: 2011 International Conference on Indoor Positioning and Indoor Navigation.pp. 1-8 (2011). https://doi.org/10.1109/IPIN.2011.6071934
• 32. Lion, D., Chiu, A., Sun, H., Zhuang, X., Grcevski, N., Yuan, D.: Don’t get caught in the cold, warm-up your jvm. In: Proceedings of the Symposium on Operating Systems Design and Implementation(OSDI’16) (2016).
• 33. Liu, K., Motta, G., Ma, T., Guo, T.: Multi-floor indoor navigation with geomagnetic field positioningand ant colony optimization algorithm pp. 314-323 (2016). https://doi.org/10.1109/SOSE.2016.18
• 34. Liu, Q., Yang, J., Huang, D.: Research on path planning for intelligent mobile robots basedon improved a* algorithm. Symmetry16(10), 1311 (2024). https://doi.org/10.3390/sym16101311,
• https://www.mdpi.com/2073-8994/16/10/1311
• 35. Manlises, C., Yumang, A., Marcelo, M., Adriano, A., Reyes, J.: Indoor navigation system basedon computer vision using camshift and d* algorithm for visually impaired pp. 481-484 (2016). https://doi.org/10.1109/ICCSCE.2016.7893623
• 36. Mikulowski, D., Salamonczyk, A., Niewiadomski, A., Pilski, M., Terlikowski, G., Switalski, P.:An approach to provide a universal structural map to aid navigation inside campus buildings usingbeacons and mobile devices. In: Bastiaens, T. (ed.) Proceedings of EdMedia + Innovate Learning2023. pp. 1198-1203. Association for the Advancement of Computing in Education (AACE), Vienna, Austria (July 2023), https://www.learntechlib.org/p/222636
• 37. Mikułowski, D., Niewiadomski, A., Salamończyk, A., Pilski, M., Świtalski, P., Terlikowski, G.:Supporting independent navigation of disabled students in university campus using beacons andontology map. In: Bastiaens, T. (ed.) Proceedings of EdMedia + Innovate Learning 2022. pp. 1005-1010. Association for the Advancement of Computing in Education (AACE), Online (November2022).
• 38. Mikułowski, D., Salamończyk, A., Świtalski, P., Niewiadomski, A., Terlikowski, G., Pilski, M.:Supporting user positioning and navigation inside campus buildings using ble transmitters andgeometric methods. In: Bastiaens, T. (ed.) Proceedings of EdMedia + Innovate Learning 2024. pp.93-102. Association for the Advancement of Computing in Education (AACE), Brussels, Belgium(July 2024).
• 39. Nazarczuk, M.: Moduł wyznaczania ścieżki dla systemu NaviSecure (in Polish). Master’s thesis, Uniwersytet Przyrodniczo-Humanistyczny w Siedlcach, Siedlce (September 2023).
• 40. Needham, M., Hodler, A.E.: Graph algorithms: practical examples in Apache Spark and Neo4j.O’Reilly Media (2019).
• 41. Pala, M., Osati Eraghi, N., López-Colino, F., Sánchez, A., De Castro, A., Garrido, J.: Hctnav: Apath planning algorithm for low-cost autonomous robot navigation in indoor environments. ISPRSInternational Journal of Geo-Information2, 729-748 (08 2013). https://doi.org/10.3390/ijgi2030729
• 42. Patel, A.: A*’s use of the heuristic. http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html, [Accessed 12-07-2023].
• 43. Prandi, C., Barricelli, B., Mirri, S., Fogli, D.: Accessible wayfinding and navigation: a systematicmapping study. Universal Access in the Information Society22(09 2021). https://doi.org/10.1007/s10209-021-00843-x
• 44. Richter, J., Lorenz, J., Costantino, M., Traubinger, V., Tauchmann, N., Graichen, T., Heinkel, U.:Dynamic indoor navigation and orientation system for people with impairments. pp. 473-477 (092020). https://doi.org/10.1145/3404983.3410000
• 45. Singh, J., Kaur, H., Johnson, M.T., et al.: 3d indoor modeling and game theory based navigationfor pre and post covid-19 situation. Frontiers in Public Health11, 123-132 (2023). https://doi.org/10.3389/fpubh.2023.012345
• 46. Switalski, P., Salamonczyk, A.: Universal structural map for indoor navigation in university campus. Studia Informatica. System and information technology29(2), 69-79 (2023).
• 47. Zaniewicz, N., Salamończyk, A.: Comparison of Mongo DB, Neo4j and Arango DB databases usingthe developed data generator for NoSQL databases. Studia Informatica. System and information technology 26(1), 61-72 (Nov 022). https://doi.org/10.34739/si.2022.26.04

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).