“Automata-Theoretic Approaches to Planning in Robotics”
Thursday, Jan. 20 at 1:00pm
Email firstname.lastname@example.org for Zoom info
This talk will present a collection of new planning algorithms that enable robots to achieve complex goals, beyond simple point-to-point path planning, using automata-theoretic methods. We consider a variety of problems, including planning for what parts of the world to observe, where to monitor other agents’ movements, and how to achieve desired temporally-extended behaviors in spite of conflicting constraints. In an automata-theoretic approach for planning, usually all possible behaviors of the system are modeled using a discrete model and all desired behaviors for planning are modeled using an automaton, and then the planning problem is solved on a product automaton made from the model and the automaton. In this talk, we present several planning problems solved using this approach. First, we consider a problem in which a robot is tasked with observing an uncertain time-extended process to produce a `chronicle’ of occurrent events that meets a given specification. This problem is especially useful in applications where we deploy robots to autonomously make structured videos or documentaries of events occurring in an unpredictable environment. We also discuss a multi-robot extension of the same problem. Next, we consider the problem of planning where to observe the behavior of an agent to ensure that the agent’s execution within the environment fits a pre-disclosed itinerary. This problem arises in a range of contexts including in validating safety claims about robot behavior, applications in security and surveillance, and for both the conception and the (physical) design and logistics of scientific experiments. We prove that this problem is computationally hard and propose an integer linear programming formulation that is capable of solving problem instances of moderate size. Then, we study linear temporal logic planning under conflicting soft specifications. We specifically focus on generating a `shortest’ desired behavior, which we show is computationally hard to synthesize on the product automaton, and thus, propose a greedy algorithm. Finally, we discuss several future directions of these problems.
Hazhar Rahmani is currently a PhD candidate in Computer Science, working under supervision of Jason M. O’Kane in the Department of Computer Science and Engineering at University of South Carolina. His research interests include algorithmic robotics, planning in robotics, formal methods in robotics, and computational geometry.