Papers

We introduce a novel method for encoding cost optimal delete-free STRIPS Planning as SAT. Our method is based on representing any relaxed plan as a partial function from the set of propositions to the set of actions. This function can map any proposition to a unique action that adds the proposition during execution of the relaxed plan. We show that a relaxed plan can be produced by maintaining acyclicity in the graph of all causal relations among propositions, represented by the mentioned partial function. We also show that by efficient encoding of action cost propagation and enforcing a series of upper bounds on the total costs of the output plan, an optimal plan can effectively be produced for a given delete-free STRIPS problem. Our empirical results indicate that this method is quite competitive with the state-of-the-art, demonstrating a better coverage compared to that of competing methods on conventional STRIPS planning problems.

poster session 1 @ blue 4, poster session 11 @ blue 4, oral session 1 @ blue 4, poster session 1, poster session 11, oral session 1

Much of the research on learning symbolic models of AI agents focuses on agents with stationary models. This assumption fails to hold in settings where the agent’s capabilities may change as a result of learning, adaptation, or other post-deployment modifications. Efficient assessment of agents in such settings is critical for learning the true capabilities of an AI system and for ensuring its safe usage. In this work, we propose a novel approach to differentially assess black-box AI agents that have drifted from their prior known models. As a starting point, we consider the fully observable and deterministic setting. We leverage observations of the agent’s current behavior and knowledge of the initial model to generate an active querying policy that selectively queries the agent and computes an updated model of its functionality. Empirical evaluation shows that our approach is much more efficient than re-learning the agent model from scratch. We also show that the cost of differential assessment using our method is proportional to the amount of drift in the agent’s functionality.

poster session 1 @ blue 4, poster session 11 @ blue 4, oral session 1 @ blue 4, poster session 1, poster session 11, oral session 1

We consider the problem of learning models of stochastic environments for planning, assuming that the transitions on the various state factors are independent. We suppose we have example trajectories of policies for random problems executing in an unknown environment, and we would like to match the rate of success of those policies. We present a polynomial-time algorithm that, given a polynomial number of trajectories, produces a PPDDL model such that optimal policies under the PPDDL model will provably achieve a success rate at future goals that is almost as good or better than the policies that produced the training trajectories. Moreover, we also consider a variant of PPDDL in which there is uncertainty about the transition probabilities, specified by an interval for each factor that contains the respective true transition probabilities. We also give a polynomial-time algorithm that, when given the example trajectories, produces such an imprecise-PPDDL environment model and guarantees that with high probability, the true environment is indeed captured by the uncertain parameters, while also guaranteeing that the optimal bound on the success probability in this model is almost as good or better than the success rate of the policies that produced the training examples.

poster session 1 @ blue 4, poster session 11 @ blue 4, oral session 1 @ blue 4, poster session 1, poster session 11, oral session 1