Computer Science Graduate Seminar
Wednesday, September 20, 2023, 2:00pm
Towards Bridging the Gap between High-Level Reasoning and Execution on Robots
- Till Hofmann, M.Sc.
- Place: Computer Science Center, 5053.2 (B-IT)
- Hybrid: Zoom Link
When reasoning about actions, e.g., by means of task planning or agent programming with Golog, the robot's actions are typically modeled on an abstract level, where complex actions such as picking up an object are treated as atomic primitives with deterministic effects and preconditions that only depend on the current state. However, executing such an action on a robot is a complex task involving multiple steps with additional temporal preconditions and timing constraints. Furthermore, the action may be noisy, e.g., producing erroneous sensing results and not always having the desired effects. While these aspects are typically ignored in reasoning tasks, they need to be dealt with during execution. In this thesis, we propose several approaches towards closing this gap.
Based on a variant of the situation calculus that incorporates metric time and metric temporal logic, we propose modeling the robot platform with timed automata and temporal constraints to describe the connection between the high-level actions and the robot platform. We then describe two approaches towards transforming the high-level program. First, we view the transformation as a synthesis problem, where the task is to synthesize a controller that executes the program while satisfying the specification, independent of the environment's choices. We show that the synthesis problem is decidable, describe an algorithm to construct a controller, and evaluate the approach in two robotics scenarios. While this approach supports controlling Golog programs against a specification with timing constraints, the synthesis problem has non-primitive recursive complexity and therefore does not scale well. For this reason, we describe a second approach based on some simplifying assumptions which allow us to view the transformation problem as a reachability problem on timed automata, which can be solved with state-of-the-art tools. We demonstrate the effectiveness and scalability of the approach in a number of scenarios.
Finally, we turn towards noisy sensors and effectors. Based on DS, a probabilistic variant of the situation calculus that allows modeling the agent's degree of belief, we describe an abstraction framework for Golog programs with noisy actions. In this framework, a high-level and non-stochastic program is mapped to a more detailed and stochastic low-level program. As the high-level program is non-stochastic, we may use non-probabilistic reasoning methods such as task planning. At the same time, by mapping the abstract actions to low-level programs, we may still deal with uncertainty during execution. We define a suitable notion of bisimulation that guarantees the equivalence between the high-level and low-level programs and demonstrate the approach with an example.
The computer science lecturers invite interested people to join.