Optimal placement of UV-based communications relay nodes. (English) Zbl 1205.90202
Summary: We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem.
Keywords:
unmanned vehicles; global optimization; hop-restricted shortest paths; Pareto solution; label correcting algorithmsSoftware:
VisiLibityReferences:
| [1] | Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, NJ (1993) · Zbl 1201.90001 |
| [2] | Anderson, S.O., Simmons, R., Goldberg, D.: Maintaining line of sight communications network between planetary rovers. In: Proceedings of the 2003 IEEE/RSJ International Conference of Intelligent Robots and Systems, pp. 2266–2272. IEEE (2003) |
| [3] | Anisi, D.A., Ögren, P., Hu, X.: Communication constrained multi-UGV surveillance. In: Proceedings of the 17th IFAC World Congress, Seoul, South Korea, 6–11 July 2008 |
| [4] | Arkin, R.C., Diaz, J.: Line-of-sight constrained exploration for reactive multiagent robotic teams. In: 7th International Workshop on Advanced Motion Control, pp. 455–461 (2002) |
| [5] | Balakrishnan A., Altinkemer K.: Using a hop-constrained model to generate alternative communication network design. ORSA J. Comput. 4(2), 192–205 (1992) · Zbl 0825.90395 |
| [6] | Bellman R.: On a routing problem. Q. Appl. Math. 16(1), 87–90 (1958) · Zbl 0081.14403 |
| [7] | Ben-Moshe B., Carmi P., Katz M.J.: Approximating the visible region of a point on a terrain. GeoInformatica 12(1), 21–36 (2008) · doi:10.1007/s10707-006-0017-5 |
| [8] | Bertsekas D.P.: Dynamic Programming and Optimal Control. Athena Scientific, Belmont, MA (1995) · Zbl 0904.90170 |
| [9] | Bertsekas D.P.: Network Optimization: Continuous and Discrete Models. Athena Scientific, Belmont, MA (1998) · Zbl 0997.90505 |
| [10] | Burdakov, O., Holmberg, K., Olsson, P.-M.: A dual ascent method for the hop-constrained shortest path problem with application to positioning of unmanned aerial vehicles. Technical Report LiTH-MAT-R-2008-07, Department of Mathematics, Linköping University (2008) |
| [11] | Burdakov, O., Doherty, P., Holmberg, K., Kvarnström, J., Olsson, P.-M.: Positioning unmanned aerial vehicles as communication relays for surveillance tasks. In: Proceedings of Robotics: Science and Systems, Seattle, USA (2009) |
| [12] | Cherkassky B.V., Goldberg A.V., Radzik T.: Shortest paths algorithms: theory and experimental evaluation. Math. Program. 73(2), 129–174 (1996) · Zbl 0853.90111 |
| [13] | Choset H., Lynch K.M., Hutchinson S., Kantor G., Burgard W., Kavraki L.E., Thrun S.: Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Cambridge, MA (2005) · Zbl 1081.68700 |
| [14] | Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, 2nd edn. MIT Press/McGraw-Hill, Cambridge/New York (2001) · Zbl 1047.68161 |
| [15] | De Floriani L., Magillo P.: Algorithms for visibility computation on terrains: a survey. Environ. Plann. B Plann. Des. 30(5), 709–728 (2003) · doi:10.1068/b12979 |
| [16] | Doherty, P.: Advanced research with autonomous unmanned aerial vehicles. In: Proceedings on the 9th International Conference on Principles of Knowledge Representation and Reasoning (2004) |
| [17] | Doherty, P., Rudol, P.: A UAV search and rescue scenario with human body detection and geolocalization. In: 20th Australian Joint Conference on Artificial Intelligence (AI07) (2007) |
| [18] | Dumitrescu I., Boland N.: Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem. Networks 42(3), 135–153 (2003) · Zbl 1031.68144 · doi:10.1002/net.10090 |
| [19] | Dynia, M., Kutylowski, J., auf der Heide, F.M., Schrieb, J.: Local strategies for maintaining a chain of relay stations between an explorer and a base station. In: SPAA ’07: Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 260–269. ACM Press, New York, USA, 1 Jan 2007 |
| [20] | Ford L.R. Jr, Fulkerson D.R.: Flows in Networks. Princeton University Press, Princeton, NJ (1962) · Zbl 0106.34802 |
| [21] | Fridman, A., Modi, J., Weber, S., Kam, M.: Communication-based motion planning. In: Proceedings of 41st Annual Conference on Information Sciences and Systems, pp. 382–387. IEEE (2007) |
| [22] | Ghosh S.K.: Visibility Algorithms in the Plane. Cambridge University Press, Cambridge, MA (2007) · Zbl 1149.68076 |
| [23] | Guérin R., Orda A.: Computing shortest paths for any number of hops. IEEE/ACM Trans. Netw. 10(5), 613–620 (2002) · doi:10.1109/TNET.2002.803917 |
| [24] | LaValle S.M.: Planning Algorithms. Cambridge University Press, Cambridge, MA (2006) · Zbl 1100.68108 |
| [25] | Lawler E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976) · Zbl 0413.90040 |
| [26] | Leighton F.T., Rosenberg A.L.: Three-dimensional circuit layouts. SIAM J. Comput. 15(3), 793–813 (1986) · Zbl 0612.68063 · doi:10.1137/0215057 |
| [27] | Moitra A., Mattheyses R.M., DiDomizio V.A., Hoebel L.J., Szczerba R.J., Yamrom B.: Multivehicle reconnaissance route and sensor planning. IEEE Trans. Aerosp. Electron. Syst. 39(3), 799–812 (2003) · doi:10.1109/TAES.2003.1238737 |
| [28] | Nagy G.: Terrain visibility. Comput. Graph. 18(6), 763–773 (1994) · doi:10.1016/0097-8493(94)90002-7 |
| [29] | Obermeyer, K.J.: The VisiLibity library. http://www.VisiLibity.org (2008) |
| [30] | Pereira, G.A.S., Das, A.K., Kumar, V., Campos, M.F.M.: Decentralized motion planning for multiple robots subject to sensing and communication constraints. In: Proceedings of the Second Multi-Robot Systems Workshop, pp. 267–278. Kluwer Academic Press (2003) |
| [31] | Pezeshkian, N., Nguyen, H.G., Burmeister, A.: Unmanned ground vehicle radio relay deployment system for non-line-of-sight operations. In: Proceedings of IASTED International Conference on Robotics and Applications. ACTA Press (2007) |
| [32] | Pinkney, M.F.J., Hampel, D., DiPierro, S.: Unmanned aerial vehicle (uav) communications relay. In: Military Communications Conference MILCOM’96, vol. 1, pp. 45–51. IEEE (1996) |
| [33] | Pirkul H., Soni S.: New formulations and solution procedures for the hop constrained network design problem. Eur. J. Oper. Res. 148(1), 126–140 (2003) · Zbl 1036.90501 · doi:10.1016/S0377-2217(02)00366-1 |
| [34] | Schouwenaars T., Stubbs A., Paduano J., Feron E.: Multivehicle path planning for nonline-of-sight communication. J. Field Rob. 23(3–4), 269–290 (2006) · doi:10.1002/rob.20119 |
| [35] | Sridharan K., Priya T.K.: A hardware accelerator and fpga realization for reduced visibility graph construction using efficient bit representations. IEEE Trans. Ind. Electron. 54(3), 1800–1804 (2007) · doi:10.1109/TIE.2007.894726 |
| [36] | Stewart A.J.: Fast horizon computation at all points of a terrain with visibility and shading applications. IEEE Trans. Vis. Comput. Graph. 4(1), 82–93 (1998) · doi:10.1109/2945.675656 |
| [37] | Szczerba, R.J., Chen, D.Z., Klenk, K.S.: Minimum turns/shortest path problems: a framed-subspace approach. In: Proceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics, vol. 1, pp. 398–403. IEEE (1997) |
| [38] | Szeszler, D.: Combinatorial algorithms in VLSI routing. PhD thesis, Budapest University of Technology and Economics (2005) |
| [39] | Tandy, C.R.V.: The isovist method of landscape survey. In: Murray, H.C. (ed.) Symposium on Methods of Landscape Analysis, pp. 9–10. Landscape Research Group, London (1967) |
| [40] | Turner A., Doxa M., O’Sullivan D., Penn A.: From isovists to visibility graphs: a methodology for the analysis of architectural space. Environ. Plann. B Plann. Des. 28, 103–121 (2001) · doi:10.1068/b2684 |
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.
