Probabilistic planning with formal performance guarantees for mobile service robots

被引:50
作者
Lacerda, Bruno [1 ]
Faruq, Fatma [2 ]
Parker, David [2 ]
Hawes, Nick [1 ]
机构
[1] Univ Oxford, Oxford Robot Inst, 23 Banbury Rd, Oxford OX2 6NN, England
[2] Univ Birmingham, Sch Comp Sci, Birmingham, W Midlands, England
基金
英国工程与自然科学研究理事会; 英国科研创新办公室;
关键词
Mobile service robots; planning under uncertainty; Markov decision processes; linear temporal logic; MOTION;
D O I
10.1177/0278364919856695
中图分类号
TP24 [机器人技术];
学科分类号
080202 ; 1405 ;
摘要
We present a framework for mobile service robot task planning and execution, based on the use of probabilistic verification techniques for the generation of optimal policies with attached formal performance guarantees. Our approach is based on a Markov decision process model of the robot in its environment, encompassing a topological map where nodes represent relevant locations in the environment, and a range of tasks that can be executed in different locations. The navigation in the topological map is modeled stochastically for a specific time of day. This is done by using spatio-temporal models that provide, for a given time of day, the probability of successfully navigating between two topological nodes, and the expected time to do so. We then present a methodology to generate cost optimal policies for tasks specified in co-safe linear temporal logic. Our key contribution is to address scenarios in which the task may not be achievable with probability one. We introduce a task progression function and present an approach to generate policies that are formally guaranteed to, in decreasing order of priority: maximize the probability of finishing the task; maximize progress towards completion, if this is not possible; and minimize the expected time or cost required. We illustrate and evaluate our approach with a scalability evaluation in a simulated scenario, and report on its implementation in a robot performing service tasks in an office environment for long periods of time.
引用
收藏
页码:1098 / 1123
页数:26
相关论文
共 54 条
[1]  
[Anonymous], 1976, DENUMERABLE MARKOV C, DOI DOI 10.1007/978-1-4684-9455-6
[2]  
[Anonymous], 2012, AAAI
[3]  
Baier C, 2008, PRINCIPLES OF MODEL CHECKING, P1
[4]  
Baier C., 2014, TOOLS ALGORITHMS CON
[5]   Symbolic planning and control of robot motion - Finding the missing pieces of current methods and ideas [J].
Belta, Calin ;
Bicchi, Antonio ;
Egerstedt, Magnus ;
Frazzoli, Emilio ;
Klavins, Eric ;
Pappas, George J. .
IEEE ROBOTICS & AUTOMATION MAGAZINE, 2007, 14 (01) :61-70
[6]  
Bhatia A, 2010, P 2010 IEEE INT C RO
[7]   Motion Planning with Complex Goals A Multilayered Synergistic Approach [J].
Bhatia, Amit ;
Maly, Matthew R. ;
Kavraki, Lydia E. ;
Vardi, Moshe Y. .
IEEE ROBOTICS & AUTOMATION MAGAZINE, 2011, 18 (03) :55-64
[8]  
Boutilier C, 1999, J ARTIF INTELL RES, V11, P1
[9]  
Cashmore M, 2015, P 25 INT C PLANN SCH
[10]  
Castro L., 2013, P 52 IEEE C DEC CONT