Ignorance & Nondeterminism in Planning & Reactive Synthesis

This project focuses on improving the ability of artificial intelligence systems to make decisions in situations where very little is known about the environment. Current AI agents perform well when they can estimate probabilities and calculate risks, but they struggle when such information is unavailable. In many real-world scenarios --- such as autonomous robots operating in unfamiliar settings or software systems responding to unpredictable user behavior --- agents must act without reliable data. Traditional approaches aim to find strategies that guarantee success, but in many cases, these strategies do not exist, leaving a significant gap in decision-making under uncertainty. To address this challenge, the research introduces the concept of best-effort solutions. Rather than seeking perfect plans, which may be impossible, best-effort strategies aim to achieve the most favorable outcome given the limited information available. These strategies are guaranteed to exist, making them a practical alternative to current methods. The project will develop theoretical foundations, analyze computational complexity, and design algorithms to support these solutions. It will also create prototype implementations to demonstrate their feasibility. We aim to lift best-effort solutions from the basic setting to help materialize their exciting potential to replace standard solutions in the face of ignorance. We will also study best-effort solutions in combination with other rules for making decisions under ignorance, as well as exploring some of these rules on their own. We will provide novel theoretical foundations, complexity results, and synthesis and verification algorithms. Finally, using cutting-edge techniques, some of which have only been applied in classical settings, we will provide prototype implementations of selected algorithms. The work combines advanced techniques from logic, decision theory, and computer science. By extending ideas from a successful pilot study, the project seeks to establish best-effort solutions as a standard approach for decision-making under ignorance. This innovation has the potential to transform how AI systems operate in uncertain environments, enabling them to act intelligently even when little is known about the environment.