×

zbMATH — the first resource for mathematics

On vehicle placement to intercept moving targets. (English) Zbl 1229.93163
Summary: We address optimal placement of vehicles with simple motion to intercept a mobile target that is generated stochastically on a line segment. The optimality of vehicle placement is measured through a cost function associated with intercepting the target. With a single vehicle, we assume that the target moves (i) with fixed speed and in a fixed direction perpendicular to the line segment, or (ii) to maximize the distance from the line segment, or (iii) to maximize intercept time. In each case, we show that the cost function is strictly convex, its gradient is smooth, and the optimal vehicle placement is obtained by a standard gradient-based optimization technique. With multiple vehicles, we assume that the target moves with fixed speed and in a fixed direction perpendicular to the line segment. We present a discrete-time partitioning and gradient-based algorithm, and characterize conditions under which the algorithm asymptotically leads the vehicles to a set of critical configurations of the cost function.

MSC:
93E20 Optimal stochastic control
49N75 Pursuit and evasion games
93A14 Decentralized systems
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Bopardikar, S.D.; Smith, S.L.; Bullo, F.; Hespanha, J.P., Dynamic vehicle routing for translating demands: stability analysis and receding-horizon policies, IEEE transactions on automatic control, 55, 11, 2554-2569, (2010) · Zbl 1368.90019
[2] Bopardikar, S. D., Smith, S. L., & Bullo, F. (2010b). On vehicle placement to intercept moving targets. Technical report. Available at: http://arxiv.org/pdf/1003.1423. · Zbl 1229.93163
[3] Bullo, F.; Cortés, J.; Martínez, S., (), Available at: http://www.coordinationbook.info
[4] Cortés, J.; Martínez, S.; Karatas, T.; Bullo, F., Coverage control for mobile sensing networks, IEEE transactions on robotics and automation, 20, 2, 243-255, (2004)
[5] Drezner, Z., ()
[6] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM review, 41, 4, 637-676, (1999) · Zbl 0983.65021
[7] Fekete, S.P.; Mitchell, J.S.B.; Beurer, K., On the continuous fermat – weber problem, Operations research, 53, 1, 61-76, (2005) · Zbl 1165.90553
[8] Girard, A. R., Howell, A. S., & Hedrick, J. K. (2004). Border patrol and surveillance missions using multiple unmanned air vehicles. In IEEE Conf. on decision and control. Paradise Island, Bahamas. (pp. 620-625).
[9] Gray, R.M.; Neuhoff, D.L., Quantization, IEEE transactions on information theory, 44, 6, 2325-2383, (1998), Commemorative Issue 1948-1998 · Zbl 1016.94016
[10] Guelman, M., A qualitative study of proportional navigation, IEEE transactions on aerospace and electronic systems, 7, 4, 637-643, (1971)
[11] Isaacs, R., Differential games, (1965), Wiley · Zbl 0152.38407
[12] Kwok, A., & Martínez, S. (2010). A coverage algorithm for drifters in a river environment. In American control conference. Baltimore, MD (pp. 6436-6441).
[13] Martínez, S.; Bullo, F., Optimal sensor placement and motion coordination for target tracking, Automatica, 42, 4, 661-668, (2006) · Zbl 1110.93050
[14] Pachter, M., Simple motion pursuit-evasion in the half-plane, Computers and mathematics with applications, 13, 1-3, 69-82, (1987) · Zbl 0622.90107
[15] Schwager, M.; Rus, D.; Slotine, J.J., Decentralized, adaptive coverage control for networked robots, International journal of robotics research, 28, 3, 357-375, (2009)
[16] Stone, L.D., Theory of optimal search, Operations research society of America, (1975) · Zbl 0343.90030
[17] Szechtman, R.; Kress, M.; Lin, K.; Cfir, D., Models of sensor operations for border surveillance, Naval research logistics, 55, 1, 27-41, (2008) · Zbl 1279.90076
[18] Zemel, E., Probabilistic analysis of geometric location problems, SIAM journal on algebraic and discrete methods, 6, 2, 189-200, (1984) · Zbl 0569.90022
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.