On the minimum-time control problem for differential drive robots with bearing constraints. (English) Zbl 1379.49002
Summary: This paper presents a study of analysis of minimum-time trajectories for a differential drive robot equipped with a fixed and limited field-of-view camera, which must keep a given landmark in view during maneuvers. Previous works have considered the same physical problem and provided a complete analysis/synthesis for the problem of determining the shortest paths. The main difference in the two cost functions (length vs. time) lays on the rotation on the spot. Indeed, this maneuver has zero cost in terms of length and hence leads to a 2D shortest path synthesis. On the other hand, in case of minimum time, the synthesis depends also on the orientations of the vehicle. In other words, the not-zero cost of the rotation on the spot maneuvers leads to a 3D minimum-time synthesis. Moreover, the shortest paths have been obtained by exploiting the geometric properties of the extremal arcs, i.e., straight lines, rotations on the spot, logarithmic spirals and involute of circles. Conversely, in terms of time, even if the extremal arcs of the minimum-time control problem are exactly the same, the geometric properties of these arcs change, leading to a completely different analysis and characterization of optimal paths. In this paper, after proving the existence of optimal trajectories and showing the extremal arcs of the problem at hand, we provide the control laws that steer the vehicle along these arcs and the time-cost along each of them. Moreover, this being a crucial step toward numerical implementation, optimal trajectories are proved to be characterized by a finite number of switching points between different extremal arcs, i.e., the concatenations of extremal arcs with infinitely many junction times are shown to violate the optimality conditions.
MSC:
| 49J15 | Existence theories for optimal control problems involving ordinary differential equations |
| 49K15 | Optimality conditions for problems involving ordinary differential equations |
| 34H05 | Control problems involving ordinary differential equations |
| 37J60 | Nonholonomic dynamical systems |
| 93C85 | Automated systems (robots, etc.) in control theory |
Keywords:
time-optimal paths; nonholonomic dynamical systems; bearing constraints; differential drive vehiclesReferences:
| [1] | Siegwart, R., Nourbakhsh, I.R., Scaramuzza, D.: Introduction to autonomous mobile robots. MIT press, Cambridge (2011) |
| [2] | Cortés, J., Martínez, S., Bullo, F.: Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions. IEEE Trans. Autom. Control 51(8), 1289-1298 (2006) · Zbl 1366.93400 · doi:10.1109/TAC.2006.878713 |
| [3] | Ghrist, R., Lavalle, S.M.: Nonpositive curvature and Pareto optimal coordination of robots. SIAM J. Control Optim. 45(5), 1697-1713 (2006) · Zbl 1181.58013 · doi:10.1137/040609860 |
| [4] | Ghrist, R.W., Koditschek, D.E.: Safe cooperative robot dynamics on graphs. SIAM J. Control Optim. 40(5), 1556-1575 (2002) · Zbl 1012.93046 · doi:10.1137/S0363012900368442 |
| [5] | Guibas, L.J., Motwani, R., Raghavan, P.: The robot localization problem. SIAM J. Comput. 26(4), 1120-1138 (1997) · Zbl 0933.70004 · doi:10.1137/S0097539792233257 |
| [6] | Zhou, X.S., Roumeliotis, S.I.: Robot-to-robot relative pose estimation from range measurements. IEEE Trans. Robot. 24(6), 1379-1393 (2008) · doi:10.1109/TRO.2008.2006251 |
| [7] | Cristofaro, A., Martinelli, A.: Optimal trajectories for multi robot localization. In: 49th IEEE Conference on Decision and Control (CDC), 2010, pp. 6358-6364. IEEE (2010) · Zbl 0767.93064 |
| [8] | Dudek, G., Romanik, K., Whitesides, S.: Localizing a robot with minimum travel. SIAM J. Comput. 27(2), 583-604 (1998) · Zbl 0907.68109 · doi:10.1137/S0097539794279201 |
| [9] | Ecker, J.G., Kupferschmid, M., Marin, S.P.: Performance of several optimization methods on robot trajectory planning problems. SIAM J. Sci. Comput. 15(6), 1401-1412 (1994) · Zbl 0810.90147 · doi:10.1137/0915084 |
| [10] | Reeds, J.A., Shepp, L.A.: Optimal paths for a car that goes both forwards and backwards. Pac. J. Math. 145, 367-393 (1990) · Zbl 1494.49027 · doi:10.2140/pjm.1990.145.367 |
| [11] | Souères, P., Boissonnat, J.D.: Optimal Trajectories for Nonholonomic Mobile Robots, vol. 229. Lecture note in control and information scienze, Souères, H., Laumond, J. P. (1998) · Zbl 0864.93076 |
| [12] | Balkcom, D., Mason, M.: Time optimal trajectories for bounded velocity differential drive vehicles. Int. J. Robot. Res. 21(3), 199-217 (2002) · doi:10.1177/027836402320556403 |
| [13] | Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2003) · Zbl 0956.68149 |
| [14] | Gans, N., Hutchinson, S.: A stable vision-based control scheme for nonholonomic vehicles to keep a landmark in the field of view. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 2196 -2201 (2007) |
| [15] | Gans, N., Hutchinson, S.: Stable visual servoing through hybrid switched system control. IEEE Trans. Robot. 23(3), 530-540 (2007) · doi:10.1109/TRO.2007.895067 |
| [16] | Murrieri, P., Fontanelli, D., Bicchi, A.: A hybrid-control approach to the parking problem of a wheeled vehicle using limited view-angle visual feedback. Int. J. Robot. Res. 23(4-5), 437-448 (2004) · doi:10.1177/0278364904042196 |
| [17] | Salaris, P., Fontanelli, D., Pallottino, L., Bicchi, A.: Shortest paths for a robot with nonholonomic and field-of-view constraints. IEEE Trans. Robot. 26(2), 269-281 (2010) · doi:10.1109/TRO.2009.2039379 |
| [18] | Salaris, P., Pallottino, L., Bicchi, A.: Shortest paths for finned, winged, legged, and wheeled vehicles with side-looking sensors. Int. J. Robot. Res. 31(8), 997-1017 (2012) · doi:10.1177/0278364912446005 |
| [19] | Salaris, P., Cristofaro, A., Pallottino, L., Bicchi, A.: Shortest paths for wheeled robots with limited field-of-view: introducing the vertical constraint. In: Proceedings of the 52nd IEEE Conference on Decision and Control, pp. 5143 -5149 (2013) |
| [20] | Salaris, P., Cristofaro, A., Pallottino, L., Bicchi, A.: Epsilon-optimal synthesis for vehicles with vertically bounded field-of-view. IEEE Trans. Autom. Control (in press) · Zbl 1360.93478 |
| [21] | Chitsaz, H., LaValle, S.M., Balkcom, D.J., Mason, M.: Minimum wheel-rotation for differential-drive mobile robots. Int. J. Robot. Res. 28(1), 66-80 (2009) · doi:10.1177/0278364908096750 |
| [22] | Balkcom, D., Mason, M.: Time-optimal trajectories for an omnidirectional vehicle. Int. J. Robot. Res. 25(10), 985-999 (2006) · doi:10.1177/0278364906069166 |
| [23] | Souères, H., Laumond, J.P.: Shortest paths synthesis for a car-like robot. IEEE Trans. Autom. Control 41(5), 672-688 (1996) · Zbl 0864.93076 · doi:10.1109/9.489204 |
| [24] | Sussmann, H., Tang, G.: Shortest paths for the Reeds-Shepp car: A worked out example of the use of geometric techniques in nonlinear optimal control. Technical report, Department of Mathematics, Rutgers University (1991) · Zbl 1194.49004 |
| [25] | Huifang, W., Yangzhou, C., Soueres, P.: A geometric algorithm to compute time-optimal trajectories for a bidirectional steered robot. IEEE Trans. Robot. 25(2), 399-413 (2009) · doi:10.1109/TRO.2009.2015610 |
| [26] | Dubins, L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math. 79(3), 457-516 (1957) · Zbl 0098.35401 · doi:10.2307/2372560 |
| [27] | Cristofaro, A., Salaris, P., Pallottino, L., Giannoni, F., Bicchi, A.: On time-optimal trajectories for differential drive vehicles with field-of-view constraints. In: Proceedings of the 53rd IEEE Conference on Decision and Control (2014, in press) · Zbl 1379.49002 |
| [28] | Lou, H.: Existence and nonexistence results of an optimal control problem by using relaxed control. SIAM J. Control Optim. 46(6), 1923-1941 (2007) · Zbl 1152.49002 · doi:10.1137/050628386 |
| [29] | Pedregal, P., Tiago, J.: Existence results for optimal control problems with some special nonlinear dependence on state and control. SIAM J. Control Optim. 48(2), 415-437 (2009) · Zbl 1194.49004 · doi:10.1137/08071805X |
| [30] | Shiller, Z., Lu, H.: Computation of path constrained time optimal motions with dynamic singularities. J. Dyn. Syst. Meas. Control 114(1), 34-40 (1992) · Zbl 0767.93064 · doi:10.1115/1.2896505 |
| [31] | Hartley, R.I., Zisserman, A.: Multiple View Geometry in Computer Vision, 2nd edn. Cambridge University Press, ISBN: 0521540518 (2004) · Zbl 1072.68104 |
| [32] | Salaris, P., Cristofaro, A., Pallottino, L.: Epsilon-optimal synthesis for nonholonomic vehicles with limited field-of-view sensors. IEEE Trans. Robot. 31(6), 1404-1418 (2015) · Zbl 1360.93478 · doi:10.1109/TRO.2015.2492878 |
| [33] | Hartl, R.F., Sethi, S.P., Vickson, R.G.: A survey of the maximum principles for optimal control problems with state constraints. SIAM Rev. 37(2), 181-218 (1995) · Zbl 0832.49013 · doi:10.1137/1037043 |
| [34] | Pontryagin, L.S.: Mathematical Theory of Optimal Processes. CRC Press, Boca Raton (1987) · Zbl 0629.26002 |
| [35] | Berkovitz, L.D., Medhin, N.G.: Nonlinear Optimal Control Theory. CRC press, Boca Raton (2012) · Zbl 1257.49001 |
| [36] | Bryson, A.E., Denham, W.F., Dreyfus, S.E.: Optimal programming problems with inequality constraints. AIAA J. 1(11), 2544-2550 (1963) · Zbl 0142.35902 · doi:10.2514/3.2107 |
| [37] | Bryson, A., Ho, Y.: Applied Optimal Control. Wiley, New York (1975) |
| [38] | Maurer, H.: On optimal control problems with bounded state variables and control appearing linearly. SIAM J. Control Opt. 15(3), 345-362 (1977) · Zbl 0358.49008 · doi:10.1137/0315023 |
| [39] | Bonnard, B., Faubourg, L., Launay, G., Trélat, E.: Optimal control with state constraints and the space shuttle re-entry problem. J. Dyn. Control Syst. 9(2), 155-199 (2003) · Zbl 1034.49014 · doi:10.1023/A:1023289721398 |
| [40] | Clarke, F.: Functional Analysis, Calculus of Variations and Optimal Control, vol. 264. Springer, Berlin (2013) · Zbl 1277.49001 |
| [41] | Johansen, T.A., Perez, T.: Unmanned aerial surveillance system for hazard collision avoidance in autonomous shipping. In: 2016 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 1056-1065 (2016) · Zbl 0358.49008 |
| [42] | Sans-Muntadas, A., Pettersen, K.Y., Brekke, E.: Vision restricted path planning and control for underactuated vehicles. IFAC-PapersOnLine 49(23), 199-206 (2016) · doi:10.1016/j.ifacol.2016.10.343 |
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.
