AF:Small: Quantified Polyhedral Programming

About This Grant

Any system that is required to respond to stimuli from its environment is called a reactive system. The system’s response is possibly to change its status or conditions and even affect its environment. Hence, a reactive system is an event-driven system reacting endlessly to external stimuli. It maintains an ongoing interaction with its environment, changing its responses accordingly. For instance, a communications protocol is a system that must respond to each stimulus, even to a fragment of input, such as a disrupted received message. In several real-world important applications, reactive systems have to handle input that is immense. Moreover, the domain of possible inputs is unpredictable. It changes continuously due to the interplay between the environmental stimuli and the responses of the system. Reactive systems are widely used to handle and control critical procedures. Air traffic control systems, programs navigating robotic devices (e.g., trains, planes) and systems controlling nuclear reactors or chemical plants processes are typical examples of such applications. Because of the massive and unpredictable input that they must handle, and the crucial nature of the tasks they perform, the primary objective of reactive systems is to be able to respond to any input given to them at any time. In the event of failures, the results may be catastrophic, depending on the nature of the task the reactive system performs. These may include critical data or information losses, economic or environmental disasters, injury or even death. Therefore, reliability and dependability are essentially the most important qualities of reactive systems. In this project, we analyze optimization problems where the solution is guaranteed to be robust against changes and disruptions in the environment. This project is concerned with modeling uncertainty through the use of mathematical programming. The models examined in this proposal consist of a set of linear constraints, together with a quantifier string. In this string, each variable is either existentially or universally quantified. We look at both the continuous and discrete versions of this problem. The continuous version of this problem is known as Quantified Linear Programming (QLP). Whereas, the discrete version, specifically the version in which each variable must take an integer value, is known as Quantified Integer Programming (QIP). The project investigates the problem of optimization in quantified linear programming. The mathematical programs utilized in this project can also be used to model problems in the field of adversarial robotics. Problems in this field are concerned with the deployment of robots to detect threats in an adversarial environment. Two such problems are the Robotic Adversarial Coverage (RAC) problem and the Closed Perimeter Patrol (CPP) problem. In the RAC problem, robots are deployed to visit nodes in an area with the purpose of identifying the threats within the area. Since the purpose of the deployment is to identify threats, the robot must visit each possible threat. However, visiting a threat may result in the loss of the robot. In the CCP problem, robots are deployed along a fixed perimeter with the purpose of detecting threats. The goal is to determine a patrol policy for each robot that will maximize the probability that an incursion is detected. This project utilizes mathematical programs to develop solutions for both of these problems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.