Lockheed Martin Robotics Seminar
Temporal Logic Planning for Mobile Robots: What happens when missions cannot be satisfied?
School of Computing, Informatics and Decision Systems Engineering
Arizona State University
Temporal logic planning methods have provided a viable path towards solving the single- and multi-robot path planning, control and coordination problems from high level formal requirements. In the existing frameworks, the prevalent assumptions are (1) that a plan always exists which satisfies the mission requirements, and (2) that there is a single stakeholder with full or partial knowledge of the environment that the robots operate in. In addition, it is typically assumed that the requirements themselves are fixed and do not change over time. However, any of these assumptions may not be valid in both off-line and on-line temporal logic planning problems. That is, multiple stakeholders and inaccurate sources of information may produce unsatisfiable missions or self-contradictory models of the world or the system. Classical temporal logic planning methods cannot handle non-consistent model environments or missions even though such inconsistencies may not affect the planning problem. In this talk, we present how the user feedback problem for unsatisfiable missions can be reduced to searching for an optimal weighted path on a graph. Albeit the general search problem is NP-complete, the graph formulation of the problem opens-up the possibility for the development of efficient approximation algorithms. We present a number of heuristics for quickly computing such user feedback and we present experimental results on the performance and scalability of our solutions. Finally, we show how inconsistencies and conflicts in the mission requirements and the model of the world can be circumvented by utilizing multi-valued temporal logics and system models.
Georgios Fainekos is an Associate Professor at the School of Computing, Informatics and Decision Systems Engineering (SCIDSE) at Arizona State University (ASU). He is director of the Cyber-Physical Systems (CPS) Lab and he is currently affiliated with the NSF I/UCR Center for Embedded Systems (CES) at ASU. He received his Ph.D. in Computer and Information Science from the University of Pennsylvania in 2008 where he was affiliated with the GRASP laboratory. He holds a Diploma degree (B.Sc. & M.Sc.) in Mechanical Engineering from the National Technical University of Athens and an M.Sc. degree in Computer and Information Science from the University of Pennsylvania. Before joining ASU, he held a Postdoctoral Researcher position at NEC Laboratories America in the System Analysis & Verification Group. His expertise is on logic, formal verification, testing, control theory, artificial intelligence, and optimization. His research has applications to automotive systems, medical devices, autonomous (ground and aerial) vehicles, and human-robot interaction (HRI). In 2013, Dr. Fainekos received the NSF CAREER award and the ASU SCIDSE Best Researcher Junior Faculty Award. He is also recipient of the 2008 Frank Anger Memorial ACM SIGBED/SIGSOFT Student Award. His software toolbox, S-TaLiRo, for testing and monitoring of CPS has been nominated twice as a technological breakthrough by the industry. In 2016, Dr. Fainekos was the program co-Chair for the ACM International Conference on Hybrid Systems: Computation and Control (HSCC).