Path planning in a weighted planar subdivision under the Manhattan metric. (English) Zbl 1531.05129
Summary: In this paper, we consider the problem of path planning in a weighted polygonal planar subdivision. Each polygon has an associated positive weight which shows the cost of path per unit distance of movement in that polygon. The goal is to find a minimum cost path under the Manhattan metric for two given start and destination points. First, we propose an \(O(n^2)\) time and space algorithm to solve this problem, where \(n\) is the total number of vertices in the subdivision. Then, we improve the time and space complexity of the algorithm to \(O(n \log^2 n)\) and \(O(n \log n)\), respectively, by applying a divide and conquer approach. We also study the case of rectilinear regions in three dimensions and show that the minimum cost path under the Manhattan metric is obtained in \(O(n^2 \log^3 n)\) time and \(O(n^2 \log^2 n)\) space.
MSC:
| 05C38 | Paths and cycles |
| 05C12 | Distance in graphs |
| 05C35 | Extremal problems in graph theory |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Davoodi, M., Enamzadeh, H., Safari, A.: Path planning in a weighted planar subdivision under the Manhattan metric. In: CCCG, pp. 80-86 (2020) |
| [2] | Olcay, E.; Schuhmann, F.; Lohmann, B., Collective navigation of a multi-robot system in an unknown environment, Robot. Auton. Syst., 132 (2020) · doi:10.1016/j.robot.2020.103604 |
| [3] | Davoodi, M.; Abedin, M.; Banyassady, B.; Khanteimouri, P.; Mohades, A., An optimal algorithm for two robots path planning problem on the grid, Robot. Auton. Syst., 61, 12, 1406-1414 (2013) · doi:10.1016/j.robot.2013.07.012 |
| [4] | Davoodi, M., Bi-objective path planning using deterministic algorithms, Robot. Auton. Syst., 93, 105-115 (2017) · doi:10.1016/j.robot.2017.03.021 |
| [5] | Davoodi, M., Rouhani, A., Sanisales, M.: Path planning with objectives minimum length and maximum clearance. In: International Conference on Topics in Theoretical Computer Science, pp. 101-115. Springer (2020) · Zbl 07316486 |
| [6] | Maheshwari, A.; Nouri, A.; Sack, J-R, Shortest paths among transient obstacles, J. Combin. Optim., 43, 1036-1074 (2020) · Zbl 1495.90227 · doi:10.1007/s10878-020-00604-1 |
| [7] | Choset, HM; Hutchinson, S.; Lynch, KM; Kantor, G.; Burgard, W.; Kavraki, LE; Thrun, S., Principles of Robot Motion: Theory, Algorithms, and Implementation (2005), Cambridge: MIT press, Cambridge · Zbl 1081.68700 |
| [8] | LaValle, SM, Planning Algorithms (2006), Cambridge: Cambridge University Press, Cambridge · Zbl 1100.68108 · doi:10.1017/CBO9780511546877 |
| [9] | Mitchell, JS; Papadimitriou, CH, The weighted region problem: finding shortest paths through a weighted planar subdivision, J. ACM (JACM), 38, 1, 18-73 (1991) · Zbl 0799.68150 · doi:10.1145/102782.102784 |
| [10] | Chestnutt, J., Nishiwaki, K., Kuffner, J., Kagami, S.: An adaptive action model for legged navigation planning. In: 2007 7th IEEE-RAS International Conference on Humanoid Robots, pp. 196-202. IEEE (2007) |
| [11] | Mata, C.S., Mitchell, J.S.: A new algorithm for computing shortest paths in weighted planar subdivisions. In: Proceedings of the Thirteenth Annual Symposium on Computational Geometry, pp. 264-273 (1997) |
| [12] | Jaklin, N., Tibboel, M., Geraerts, R.: Computing high-quality paths in weighted regions. In: Proceedings of the Seventh International Conference on Motion in Games, pp. 77-86 (2014) |
| [13] | De Carufel, J-L; Grimm, C.; Maheshwari, A.; Owen, M.; Smid, M., A note on the unsolvability of the weighted region shortest path problem, Comput. Geom., 47, 7, 724-727 (2014) · Zbl 1292.65016 · doi:10.1016/j.comgeo.2014.02.004 |
| [14] | Aleksandrov, L.; Djidjev, HN; Guo, H.; Maheshwari, A.; Nussbaum, D.; Sack, J-R, Algorithms for approximate shortest path queries on weighted polyhedral surfaces, Discrete Comput. Geom., 44, 4, 762-801 (2010) · Zbl 1207.68411 · doi:10.1007/s00454-009-9204-0 |
| [15] | Dijkstra, EW, A note on two problems in connexion with graphs, Numer. Math., 1, 1, 269-271 (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390 |
| [16] | Fredman, ML; Tarjan, RE, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM (JACM), 34, 3, 596-615 (1987) · Zbl 1412.68048 · doi:10.1145/28869.28874 |
| [17] | Aleksandrov, L., Lanthier, M., Maheshwari, A., Sack, J.-R.: An \(\varepsilon \)-approximation algorithm for weighted shortest paths on polyhedral surfaces. In: Scandinavian Workshop on Algorithm Theory, pp. 11-22. Springer (1998) · Zbl 1504.68243 |
| [18] | Aleksandrov, L.; Maheshwari, A.; Sack, J-R, Determining approximate shortest paths on weighted polyhedral surfaces, J. ACM (JACM), 52, 1, 25-53 (2005) · Zbl 1204.68255 · doi:10.1145/1044731.1044733 |
| [19] | Sun, Z.; Reif, JH, On finding approximate optimal paths in weighted regions, J. Algorithms, 58, 1, 1-32 (2006) · Zbl 1103.68144 · doi:10.1016/j.jalgor.2004.07.004 |
| [20] | Tran, N., Dinneen, M.J., Linz, S.: Computing close to optimal weighted shortest paths in practice. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 30, pp. 291-299 (2020) |
| [21] | Aleksandrov, L.; Djidjev, H.; Maheshwari, A.; Sack, J-R, An approximation algorithm for computing shortest paths in weighted 3-d domains, Discrete Comput. Geom., 50, 1, 124-184 (2013) · Zbl 1284.68652 · doi:10.1007/s00454-013-9486-0 |
| [22] | Tran, N., Dinneen, M.J., Linz, S.: Close weighted shortest paths on 3d terrain surfaces. In: Proceedings of the 28th International Conference on Advances in Geographic Information Systems, pp. 597-607 (2020) |
| [23] | Bauernöppel, F.; Maheshwari, A.; Sack, J-R, An \(\omega (nd)\) lower bound on the number of cell crossings for weighted shortest paths in d-dimensional polyhedral structures, Comput. Geom., 107 (2022) · Zbl 1502.68300 · doi:10.1016/j.comgeo.2022.101897 |
| [24] | Lee, D.; Yang, C-D; Chen, T., Shortest rectilinear paths among weighted obstacle, Int. J. Comput. Geom. Appl., 1, 2, 109-124 (1991) · Zbl 0755.68137 · doi:10.1142/S0218195991000104 |
| [25] | Chen, DZ; Klenk, KS; Tu, H-YT, Shortest path queries among weighted obstacles in the rectilinear plane, SIAM J. Comput., 29, 4, 1223-1246 (2000) · Zbl 0947.68073 · doi:10.1137/S0097539796307194 |
| [26] | Gewali, LP; Meng, AC; Mitchell, JS; Ntafos, S., Path planning in \(0/1/ \infty\) weighted regions with applications, ORSA J. Comput., 2, 3, 253-272 (1990) · Zbl 0755.90084 · doi:10.1287/ijoc.2.3.253 |
| [27] | Gheibi, A., Maheshwari, A., Sack, J.-R.: Weighted region problem in arrangement of lines. In: CCCG, pp. 123-128 (2013) |
| [28] | Canny, J., Reif, J.: New lower bound techniques for robot motion planning problems. In: 28th Annual Symposium on Foundations of Computer Science (SFCS 1987), pp. 49-60. IEEE (1987) |
| [29] | Henzinger, MR; Klein, P.; Rao, S.; Subramanian, S., Faster shortest-path algorithms for planar graphs, J. Comput. Syst. Sci., 55, 1, 3-23 (1997) · Zbl 0880.68099 · doi:10.1006/jcss.1997.1493 |
| [30] | de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.C.: Polygon triangulation. In: Computational Geometry, pp. 45-61. Springer, Berlin (2000) · Zbl 0939.68134 |
| [31] | Balaban, I.J.: An optimal algorithm for finding segments intersections. In: Proceedings of the Eleventh Annual Symposium on Computational Geometry, pp. 211-219 (1995) |
| [32] | Chazelle, B.; Edelsbrunner, H., An optimal algorithm for intersecting line segments in the plane, J. ACM (JACM), 39, 1, 1-54 (1992) · Zbl 0799.68191 · doi:10.1145/147508.147511 |
| [33] | Clarkson, K., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in o (n (log n) 2) time. In: Proceedings of the Third Annual Symposium on Computational Geometry, pp. 251-257 (1987) |
| [34] | de Rezende, PJ; Lee, D.; Wu, Y-F, Rectilinear shortest paths in the presence of rectangular barriers, Discrete Comput. Geom., 4, 1, 41-53 (1989) · Zbl 0655.05041 · doi:10.1007/BF02187714 |
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.
