Seminar: Best-Effort Synthesis for Temporally Extended Goals in Nondeterministic Planning Domains

Tuesday 20^th October 12:00-13:00

Speaker: Gianmarco Parretti, University of Oxford

Title: Best-Effort Synthesis for Temporally Extended Goals in Nondeterministic Planning Domains

Abstract: In recent years, (Reactive) Synthesis has emerged as a powerful framework for the automated development of autonomous AI agents: given a specification of its goal and of the environment in which it operates, the agent must compute a strategy that ensures the satisfaction of the goal regardless of how the external environment unfolds its nondeterminism – called a winning strategy. While it is highly desirable that the agent uses a winning strategy, the problem is that such strategies do not always exist. In this talk, I will present best-effort strategies, a form of strategy ensuring that – when a winning strategy does not exist – the agent does its best to achieve the goal. I will consider the setting of an autonomous agent that operates in a Fully Observable Nondeterministic (FOND) Domain and whose goal is expressed in Linear Temporal Logic on finite traces (LTLf). For this setting, I will show that best-effort strategies have some notable properties: (i) they always exist; (ii) if a winning strategy exists, the best-effort strategies are exactly the winning strategies; and (iii) they can be computed in worst-case 2EXPTIME (though often much less in practice), i.e., the same as winning strategies. In fact, I will show that these properties generalize to the setting where the agent reasons simultaneously over multiple increasingly nondeterministic planning domains (aka multi-tier planning domains). Finally, I will detail on how best-effort strategies can be used to monitor the behaviour of an autonomous agent operating in a FOND domain, but whose strategy is not readily available for inspection.

Join: https://teams.microsoft.com/meet/3542095257933196?p=3PGx1hha2nCmpU8mRJ

We ask that you please familiarise yourself with the Hub’s code of conduct prior to attendance.
Please note, this talk will be recorded.