Multi-robot mission planning using evolutionary computation with incremental task addition
Tóm tắt
Mission planning asks the robot to solve complex missions, requiring the robot to execute several actions such that a complex goal condition (called mission) is satisfied. The missions can be specified by using Linear Temporal Logic or any custom domain-specific language. Here, we consider service robots in the home or office environments with multiple users, each specifying a task that together makes a mission. Conventional mission planning techniques assume that the complete mission specification is known in advance, while mission planning is incremental wherein tasks keep getting added and deleted. The exponential computational complexity of the current model verification-based approaches is not a viable solution. The paper presents an evolutionary framework for incrementally solving the problem of mission planning for the problems for which a polynomial-time verification system exists for the tasks. The optimal solution is represented in an encoding-specific format that is compiled to form a linear trajectory of the robots. Optimization is done as the robot operates. Thus, the robot at any time has a partial solution to every task that has already been executed that (along with the robot assigned to the task) cannot be altered, while a part representing the next steps of the robot to be optimized. This acts as a constraint in the continuous optimization. The proposed approach uses Dynamic Programming to integrate the solutions of tasks and as a distance function in the diversity preserving evolutionary computation since the mission constantly changes. Comparisons are made with a baseline evolutionary computation without Dynamic Programming, a non-incremental version of the proposed algorithm, and several greedy strategies. The proposed algorithm is seen to perform better than all other methods. Further, the algorithm is implemented and demonstrated on a Pioneer LX robot.
Tài liệu tham khảo
Baier C, Katoen JP (2008) Principles of model checking. MIT Press, Cambridge
Fisher M (2011) An introduction to practical formal methods using temporal logic. Wiley, West Sussex
Kress-Gazit H, Fainekos GE, Pappas GJ (2009) Temporal-logic-based reactive mission and motion planning. IEEE Trans Rob 25(6):1370–1381
Lahijanian M, Andersson SB, Belta C (2012) Temporal logic motion planning and control with probabilistic satisfaction guarantees. IEEE Trans Rob 28(2):396–409
Bhatia A, Kavraki LE, Vardi MY (2010a) Sampling-based motion planning with temporal goals. In: Proceedings of the 2010 IEEE international conference on robotics and automation, pp 2689–2696
Bhatia A, Kavraki LE, Vardi MY (2010b) Motion planning with hybrid dynamics and temporal goals. In: Proceedings of the 2010 49th IEEE conference on decision and control, pp 1108–1115
McMahon J, Plaku E (2014) Sampling-based tree search with discrete abstractions for motion planning with dynamics and temporal logic. In: Proceedings of the 2014 IEEE/RSJ international conference on intelligent robots and systems, pp 3726–3733
Svorenova M, Tumova J, Barnat J, Cerna I (2012) Attraction-based receding horizon path planning with temporal logic constraints. In: Proceedings of the 2012 IEEE 51st annual conference on decision and control, pp 6749–6754
Lahijanian M, Almagor S, Fried D, Kavraki LE, Vardi MY (2015) This time the robot settles for a cost: a quantitative approach to temporal logic planning with partial satisfaction. In: Proceedings of the twenty-ninth AAAI conference on artificial intelligence. AAAI, pp 3664–3671
Smith SL, Tumova J, Belta C, Rus D (2011) Optimal path planning for surveillance with temporal-logic constraints. Int J Robot Res 30(14):1695–1708
Svorenova M, Cerna I, Belta C (2015) Optimal temporal logic control for deterministic transition systems with probabilistic penalties. IEEE Trans Autom Control 60(6):1528–1541
Ulusoy A, Smith SL, Ding XC, Belta C, Rus D (2013) Optimality and robustness in multi-robot path planning with temporal logic constraints. Int J Robot Res 32(8):889–911
Fu J, Atanasov N, Topcu U, Pappas GJ (2016) Optimal temporal logic planning in probabilistic semantic maps. In: Proceedings of the 2016 IEEE international conference on robotics and automation, Stockholm, pp 3690–3697
Lacerda B, Parker D, Hawes N (2014) Optimal and dynamic planning for Markov decision processes with co-safe LTL specifications. In: Proceedings of the 2014 IEEE/RSJ international conference on intelligent robots and systems, pp 1511–1516
Schillinger P, Bürger M, Dimarogonas DV (2018) Simultaneous task allocation and planning for temporal logic goals in heterogeneous multi-robot systems. Int J Robot Res 37(7):818–838
Faruq F, Parker D, Laccrda B, Hawes N (2018) Simultaneous task allocation and planning under uncertainty. In: Proceedings of the 2018 IEEE/RSJ international conference on intelligent robots and systems, pp 3559–3564
Torres J, Baier JA (2015) Polynomial-time reformulations of LTL temporally extended goals into final-state goals. In: Proceedings of the international joint conference on artificial intelligence, pp 1696–1703
Camacho A, Triantafillou E, Muise C, Baier J, McIlraith S (2017) Non-deterministic planning with temporally extended goals: LTL over finite and infinite traces. In: Proceedings of the AAAI conference on artificial intelligence, vol 31, No. (1)
Menghi C, Garcia S, Pelliccione P, Tumova J (2018) Multi-robot LTL planning under uncertainty. In: Havelund K, Peleska J, Roscoe B, de Vink E (eds) Formal methods. Lecture notes in computer science, vol 10951. Springer, Cham, pp 399–417
Karaman S, Frazzoli E (2009) Sampling-based motion planning with deterministic μ-calculus specifications. In: Proceedings of the 48h IEEE conference on decision and control (CDC) held jointly with 2009 28th Chinese control conference, Shanghai, pp 2222–2229
Kuffner JJ, LaValle SM (2000) RRT-connect: an efficient approach to single-query path planning. In: Proceedings IEEE international conference on robotics and automation, pp 995–1001
LaValle SM, Kuffner JJ (1999) Randomized kinodynamic planning. In: Proceedings of the IEEE international conference on robotics and automation, pp 473—479
Kantaros Y, Zavlanos MM (2018) Temporal logic optimal control for large-scale multi-robot systems: 10400 states and beyond. In: Proceedings of the 2018 IEEE conference on decision and control, Miami Beach, FL, pp 2519–2524
Kantaros Y, Zavlanosm MM (2019) Sampling-based optimal control synthesis for multirobot systems under global temporal tasks. IEEE Trans Autom Control 64(5):1916–1931
Xidias EK, Azariadis PN (2011) Mission design for a group of autonomous guided vehicles. Robot Auton Syst 59(1):34–43
Lu L-C, Yue T-W (2019) Mission-oriented ant-team ACO for min–max MTSP. Appl Soft Comput 76:436–444
Kala R (2016) Sampling based mission planning for multiple robots. In: Proceedings of the IEEE congress on evolutionary computation, pp 662–669
Şenol MB (2019) A mixed integer programming (MIP) model for evaluating navigation and task planning of human–robot interactions (HRI). Intel Serv Robot 12:231–242
Kala R, Khan A, Diksha D, Shelly S, Sinha S (2018) Evolutionary mission planning. In: Proceedings of the 2018 IEEE congress on evolutionary computation, pp 1–8
Edelkamp S, Jabbar S, Nazih M (2006) Large-scale optimal PDDL3 planning with MIPS-XXL. In: 5th international planning competition booklet
Gerevini A, Haslum P, Long D, Saetti A, Dimopoulos Y (2009) Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners. Artif Intell 173(5–6):619–668
Cambon S, Alami R, Gravot F (2009) A hybrid approach to intricate motion, manipulation and task planning. Int J Robot Res 28(1):104–126
Galindo C, Fernandez-Madrigal J, Gonzalez J (2008) Multihierarchical interactive task planning: application to mobile robotics. IEEE Trans Syst Man Cybern Part B Cybern 38(3):785–798
Srivastava S, Fang E, Riano L, Chitnis R, Russell S, Abbeel P (2014) Combined task and motion planning through an extensible planner-independent interface layer. In: Proceedings of the 2014 IEEE international conference on robotics and automation, Hong Kong, pp 639–646
Matoui F, Boussaid B, Metoui B et al (2020) Contribution to the path planning of a multi-robot system: centralized architecture. Intel Serv Robot 13:147–158
Kala R (2018) On repelling robotic trajectories: coordination in navigation of multiple mobile robots. Intel Serv Robot 11:79–95
Lagoudakis MG, Berhault M, Koenig S, Keskinocak P, Kleywegt AJ (2004) Simple auctions with performance guarantees for multi-robot task allocation. In: Proceedings of the 2004 IEEE/RSJ international conference on intelligent robots and systems, pp 698–705
Choset H, Lynch KM, Hutchinson S, Kantor GA, Burgard W, Kavraki LE, Thrun S (2005) Principles of robot motion: theory, algorithms, and implementations. MIT Press, Cambridge
Tiwari R, Shukla A, Kala R (2013) Intelligent planning for mobile robotics: algorithmic approaches. IGI Global Publishers, Hershey
Kavraki LE, Svestka P, Latombe JC, Overmars H (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans Robot Autom 12(4):566–580
Russell S, Norvig P (2010) Problem solving by searching. In: Artificial intelligence: a modern approach. Pearson, Upper Saddle River, pp 64–119