Event-driven optimal control for a robotic exploration, pick-up and delivery problem. (English) Zbl 1408.93087
Summary: This paper addresses an optimal control problem (OCP) for a robot that has to find and collect a finite number of objects and move them to a depot in minimum time. The robot has fourth-order dynamics that change instantaneously at any pick-up or drop-off of an object. The objects are represented by point masses in a bounded two-dimensional space that may contain unknown obstacles. The OCP is formulated assuming either a worst-case positioning, or a uniform distribution of the objects (probabilistic case). Modeling the robotic problem by a hybrid system facilitates an event-driven receding horizon solution based on motion parameterization and gradient-based optimization. A comparison of the proposed methods to two simple heuristic approaches in simulation suggests that the event-driven approach offers significant advantages – a lower execution time (on average) and the ability to handle obstacles – over the simple solutions, at the price of a moderately increased computational effort. The methods are relevant for various robotic applications, e.g. the motion control of mobile manipulators for home-care, search and rescue, harvesting, manufacturing etc.
MSC:
| 93C85 | Automated systems (robots, etc.) in control theory |
| 93E20 | Optimal stochastic control |
| 49N90 | Applications of optimal control and differential games |
| 93C30 | Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) |
| 93C20 | Control/observation systems governed by partial differential equations |
| 93-04 | Software, source code, etc. for problems pertaining to systems and control theory |
References:
| [1] | Thrun, S.; Burgard, W.; Fox, D., Probabilistic Robotics (2008), MIT Press |
| [2] | Bryson, A. E.; Ho, Y. C., Applied Optimal Control : Optimization, Estimation, and Control (1975), John Wiley and Sons: John Wiley and Sons New York |
| [3] | F. Clarke, Discontinuous feedback and nonlinear systems, in: Proc. of IFAC Symp. on Nonlinear Control Systems, NOLCOS, 2010.; F. Clarke, Discontinuous feedback and nonlinear systems, in: Proc. of IFAC Symp. on Nonlinear Control Systems, NOLCOS, 2010. |
| [4] | Feng, D.; Krogh, B. H., Acceleration-constrained time-optimal control in n dimensions, IEEE Trans. Automat. Control, 31, 10, 955-958 (1986) · Zbl 0599.49011 |
| [5] | Mitchell, I.; Bayen, A.; Tomlin, C., A time-dependent hamilton-jacobi formulation of reachable sets for continuous dynamic games, IEEE Trans. Automat. Control, 50, 7, 947-957 (2005) · Zbl 1366.91022 |
| [6] | Grieder, P.; Kvasnica, M.; Baotić, M.; Morari, M., Stabilizing low complexity feedback control of constrained piecewise affine systems, Automatica, 41, 10, 1683-1694 (2005) · Zbl 1087.93047 |
| [7] | Applegate, D.; Bixby, R.; Chvátal, V.; Cook, W., (The Traveling Salesman Problem: A Computational Study: A Computational Study. The Traveling Salesman Problem: A Computational Study: A Computational Study, Princeton Series in Applied Mathematics (2011), Princeton University Press) · Zbl 1130.90036 |
| [8] | Toth, P.; Vigo, D., Vehicle Routing : Problems, Methods, and Applications (2015), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA |
| [9] | Seatzu, C.; Corona, D.; Giua, A.; Bemporad, A., Optimal control of continuous-time switched affine systems, IEEE Trans. Automat. Control, 51, 726-741 (2006) · Zbl 1366.49038 |
| [10] | V. Nenchev, C. Belta, J. Raisch, Optimal motion planning with temporal logic and switching constraints, in: 14th European Control Conf. (ECC’15), Linz, Austria, 2015, pp. 1135-1140.; V. Nenchev, C. Belta, J. Raisch, Optimal motion planning with temporal logic and switching constraints, in: 14th European Control Conf. (ECC’15), Linz, Austria, 2015, pp. 1135-1140. |
| [11] | B. Passenberg, O. Stursberg, Graph search for optimizing the discrete location sequence in hybrid optimal control, in: 3rd IFAC Conf. on Analysis and Design of Hybrid Systems, 2009, pp. 304-309.; B. Passenberg, O. Stursberg, Graph search for optimizing the discrete location sequence in hybrid optimal control, in: 3rd IFAC Conf. on Analysis and Design of Hybrid Systems, 2009, pp. 304-309. |
| [12] | (Cassandras, C. G.; Lygeros, J., Stochastic Hybrid Systems (2010), CRC Press) · Zbl 1123.93004 |
| [13] | Bellman, R., An optimal search problem, SIAM Rev., 5 (1963) · Zbl 0146.35604 |
| [14] | Stone, L., Theory of Optimal Search, Mathematics in Science and Engineering (1976), Elsevier Science |
| [15] | Guibas, L. J.; Latombe, J.-C.; Lavalle, S. M.; Lin, D.; Motwani, R., A visibility-based pursuit-evasion problem, Internat. J. Comput. Geom. Appl., 9, 471-494 (1996) |
| [16] | Alpern, S.; Gal, S., The Theory of Search Games and Rendezvous (2003), Kluwer’s Int. Ser. in Oper. Research & Management Science · Zbl 1034.91017 |
| [17] | Kao, M.; Reif, J.; Tate, S., Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem, Inform. and Comput., 131, 1, 63-80 (1996) · Zbl 0876.68030 |
| [18] | Cortes, J.; Martinez, S.; Karatas, T.; Bullo, F., Coverage control for mobile sensing networks, IEEE Trans. Robot. Autom., 20, 2, 243-255 (2004) |
| [19] | Zhong, M.; Cassandras, C. G., Distributed coverage control and data collection with mobile sensor networks, IEEE Trans. Automat. Control, 56, 10, 2445-2455 (2011) · Zbl 1368.90042 |
| [20] | J. Le Ny, G. Pappas, On trajectory optimization for active sensing in gaussian process models, in: Proc. of 48th IEEE Conf. on Decision and Control (CDC) held jointly with 28th Chinese Control Conference (CCC), 2009, pp. 6286-6292.; J. Le Ny, G. Pappas, On trajectory optimization for active sensing in gaussian process models, in: Proc. of 48th IEEE Conf. on Decision and Control (CDC) held jointly with 28th Chinese Control Conference (CCC), 2009, pp. 6286-6292. |
| [21] | Smith, S.; Schwager, M.; Rus, D., Persistent robotic tasks: Monitoring and sweeping in changing environments, IEEE Trans. Robot., 28, 2, 410-426 (2012) |
| [22] | Cassandras, C.; Lin, X.; Ding, X., An optimal control approach to the multi-agent persistent monitoring problem, IEEE Trans. Automat. Control, 58, 4, 947-961 (2013) · Zbl 1369.93013 |
| [23] | Molin, A.; Hirche, S., On the optimality of certainty equivalence for event-triggered control systems, IEEE Trans. Automat. Control, 58, 470-474 (2013) · Zbl 1369.93722 |
| [24] | Axelsson, H.; Boccadoro, M.; Egerstedt, M.; Valigi, P.; Wardi, Y., Optimal mode-switching for hybrid systems with varying initial states, Nonlinear Anal. Hybrid Syst., 2, 3, 765-772 (2008) · Zbl 1215.49033 |
| [25] | Rickert, M.; Sieverling, A.; Brock, O., Balancing exploration and exploitation in sampling-based motion planning, IEEE Trans. Robot., 30, 6, 1305-1317 (2014) |
| [26] | Toussaint, M., The bayesian search game, (Borenstein, Y.; Moraglio, A., Theory and Principled Methods for Designing Metaheuristics. Theory and Principled Methods for Designing Metaheuristics, Natural Computing Series (2014), Springer), 129-144 · Zbl 1328.90169 |
| [27] | C. Amato, G. Konidaris, A. Anders, G. Cruz, J.P. How, L.P. Kaelbling, Policy search for multi-robot coordination under uncertainty, in: Proc. of Robotics: Science and Systems Conf., RSS-15, 2015.; C. Amato, G. Konidaris, A. Anders, G. Cruz, J.P. How, L.P. Kaelbling, Policy search for multi-robot coordination under uncertainty, in: Proc. of Robotics: Science and Systems Conf., RSS-15, 2015. |
| [28] | Lahijanian, M.; Maly, M. R.; Fried, D.; Kavraki, L. E.; Kress-Gazit, H.; Vardi, M. Y., Iterative temporal planning in uncertain environments with partial satisfaction guarantees, IEEE Trans. Robot., 32, 3, 583-599 (2016) |
| [29] | Raman, V.; Piterman, N.; Finucane, C.; Kress-Gazit, H., Timing semantics for abstraction and execution of synthesized high-level robot control, IEEE Trans. Robot., 31, 3, 591-604 (2015) |
| [30] | K.S. Wesselowski, C.G. Cassandras, The elevator dispatching problem: Hybrid system modeling and receding horizon control, in: Proc. of 2nd IFAC Conf. on Analysis and Design of Hybrid Systems, 2006, pp. 136-141.; K.S. Wesselowski, C.G. Cassandras, The elevator dispatching problem: Hybrid system modeling and receding horizon control, in: Proc. of 2nd IFAC Conf. on Analysis and Design of Hybrid Systems, 2006, pp. 136-141. |
| [31] | Khazaeni, Y.; Cassandras, C. G., Event-driven cooperative receding horizon control for multi-agent systems in uncertain environments, IEEE Trans. Control Netw. Sys., 5, 409-422 (2018) · Zbl 1507.93145 |
| [32] | V. Nenchev, C. Belta, Receding horizon robot control in uncertain environments with temporal logic constraints, in: 15th European Control Conf., ECC’16, 2016, pp. 2614-2619.; V. Nenchev, C. Belta, Receding horizon robot control in uncertain environments with temporal logic constraints, in: 15th European Control Conf., ECC’16, 2016, pp. 2614-2619. |
| [33] | V. Nenchev, C.G. Cassandras, Optimal exploration and control for a robotic pick-up and delivery problem, in: Proc. of the 53rd Conf. on Decision and Control (CDC’14), 2014, pp. 7-12.; V. Nenchev, C.G. Cassandras, Optimal exploration and control for a robotic pick-up and delivery problem, in: Proc. of the 53rd Conf. on Decision and Control (CDC’14), 2014, pp. 7-12. |
| [34] | V. Nenchev, C.G. Cassandras, Optimal exploration and control for a robotic pick-up and delivery problem in two dimensions, in: Proc. of the 54th Conf. on Decision and Control, CDC’15, 2015, pp. 258-263.; V. Nenchev, C.G. Cassandras, Optimal exploration and control for a robotic pick-up and delivery problem in two dimensions, in: Proc. of the 54th Conf. on Decision and Control, CDC’15, 2015, pp. 258-263. |
| [35] | Cassandras, C. G.; Wardi, Y.; Panayiotou, C. G.; Yao, C., Perturbation analysis and optimization of stochastic hybrid systems, Eur. J. Control, 16, 6, 642-661 (2010) · Zbl 1216.93092 |
| [36] | V. Nenchev, J. Raisch, Towards time-optimal exploration and control by an autonomous robot, in: Proc. of 21st Mediterranean Conf. on Control and Automation (MED’13), 2013, p. 1236-1241.; V. Nenchev, J. Raisch, Towards time-optimal exploration and control by an autonomous robot, in: Proc. of 21st Mediterranean Conf. on Control and Automation (MED’13), 2013, p. 1236-1241. |
| [37] | Henzinger, T., The Theory of Hybrid Automata, 265-292 (2000), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg · Zbl 0959.68073 |
| [38] | Verscheure, D.; Demeulenaere, B.; Swevers, J.; Schutter, J. D.; Diehl, M., Time-optimal path tracking for robots: A convex optimization approach, IEEE Trans. Automat. Control, 54, 10, 2318-2327 (2009) · Zbl 1367.90088 |
| [39] | Gol, E. A.; Lazar, M.; Belta, C., Language-guided controller synthesis for linear systems, IEEE Trans. Automat. Control, 59, 5, 1163-1176 (2014) · Zbl 1360.93424 |
| [40] | Bertsekas, D. P., Constrained Optimization and Lagrange Multiplier Methods (1996), Athena Scientific |
| [41] | Nocedal, J.; Wright, S., Numerical Optimization (2006), Springer-Verlag · Zbl 1104.65059 |
| [42] | Xu, M.; Ye, J., A smoothing augmented lagrangian method for solving simple bilevel programs, Comput. Optim. Appl., 59, 353-377 (2014) · Zbl 1326.90068 |
| [43] | Bao, G.; Cassandras, C. G., Stochastic comparison algorithm for continuous optimization with estimation, J. Optim. Theory Appl., 91, 3, 585-615 (1996) · Zbl 0866.90096 |
| [44] | Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1, 1-122 (2011) · Zbl 1229.90122 |
| [45] | Choset, H. M., Principles of Robot Motion: Theory, Algorithms, and Implementation (2005), The MIT Press · Zbl 1081.68700 |
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.
