Ronen I. Brafman

AIJ Journal 2026 Journal Article

Factored planning in partially observable and deterministic multi-agent domains

• Shashank Shekhar
• Ronen I. Brafman
• Guy Shani

We consider the problem of solving qualitative decentralized partially observable Markov decision processes (QDec-POMDPs) with deterministic actions. QDec-POMDPs model dynamic systems consisting of a collaborative team of agents acting under uncertainty and partial observability, attempting to reach a desirable goal state. They can be viewed as the multi-agent version of the contingent planning model. In this work, we extend the idea of factored planning from fully observable multi-agent planning to partial observability. Our method operates as follows: First, we simplify the multi-agent planning (MAP) problem by reducing it to a single-agent planning problem. Then, we use the solution to this single-agent problem as a skeleton plan, that each agent attempts to complete separately. We describe different variants of this idea, and in particular, suggest a method that models information about each agent’s knowledge and incorporates the idea of signaling information to other agents through actions. We perform an extensive empirical evaluation over new and old domains, demonstrating the enhanced scalability of our method.

IJCAI Conference 2025 Conference Paper

Online Planning in MDPs with Stochastic Durative Actions

• Tal Berman
• Ronen I. Brafman
• Erez Karpas

Stochastic planning problems are typically modeled as Markov Decision Processes, in which actions are assumed to be instantaneous and applied sequentially. Yet, real-world actions often have durations and are applied concurrently. This paper presents an online planning approach that can deal with durative actions with stochastic outcomes. Our approach relies on Monte Carlo Tree Search with a new backpropagation procedure and temporal reasoning techniques that address the need to not only choose which action to execute, but also when to execute it. We also introduce a novel heuristic that combines reasoning about time and probabilities. Overall, we present the first online planner for stochastic temporal planning, solving a richer problem representation than previous work while achieving state-of-the-art empirical results.

AIJ Journal 2024 Journal Article

Regular decision processes

• Ronen I. Brafman
• Giuseppe De Giacomo

We introduce and study Regular Decision Processes (RDPs), a new, compact model for domains with non-Markovian dynamics and rewards, in which the dependence on the past is regular, in the language theoretic sense. RDPs are an intermediate model between MDPs and POMDPs. They generalize k-order MDPs and can be viewed as a POMDP in which the hidden state is a regular function of the entire history. In factored RDPs, transition and reward functions are specified using formulas in linear temporal logics over finite traces, or using regular expressions. This allows specifying complex dependence on the past using intuitive and compact formulas, and building models of partially observable domains without specifying an underlying state space.

AAAI Conference 2023 Conference Paper

Probabilistic Programs as an Action Description Language

• Ronen I. Brafman
• David Tolpin
• Or Wertheim

Actions description languages (ADLs), such as STRIPS, PDDL, and RDDL specify the input format for planning algorithms. Unfortunately, their syntax is familiar to planning experts only, and not to potential users of planning technology. Moreover, this syntax limits the ability to describe complex and large domains. We argue that programming languages (PLs), and more specifically, probabilistic programming languages (PPLs), provide a more suitable alternative. PLs are familiar to all programmers, support complex data types and rich libraries for their manipulation, and have powerful constructs, such as loops, sub-routines, and local variables with which complex, realistic models and complex objectives can be simply and naturally specified. PPLs, specifically, make it easy to specify distributions, which is essential for stochastic models. The natural objection to this proposal is that PLs are opaque and too expressive, making reasoning about them difficult. However, PPLs also come with efficient inference algorithms, which, coupled with a growing body of work on sampling-based and gradient-based planning, imply that planning and execution monitoring can be carried out efficiently in practice. In this paper, we expand on this proposal, illustrating its potential with examples.

IROS Conference 2023 Conference Paper

PTDRL: Parameter Tuning Using Deep Reinforcement Learning

• Elias Goldsztejn
• Tal Feiner
• Ronen I. Brafman

A variety of autonomous navigation algorithms exist that allow robots to move around in a safe and fast manner. Many of these algorithms require parameter re-tuning when facing new environments. In this paper, we propose PTDRL, a parameter-tuning strategy that adaptively selects from a fixed set of parameters those that maximize the expected reward for a given navigation system. Our learning strategy can be used for different environments, different platforms, and different user preferences. Specifically, we attend to the problem of social navigation in indoor spaces, using a classical motion planning algorithm as our navigation system and training its parameters to optimize its behavior. Experimental results show that PTDRL can outperform other online parameter-tuning strategies.

ECAI Conference 2023 Conference Paper

Reinforcement Learning in RDPs by Combining Deep RL with Automata Learning

• Tal Shahar
• Ronen I. Brafman

Regular Decision Processes (RDPs) are a recently introduced model for decision-making in non-Markovian domains in which states are not postulated a-priori, and the next observation depends in a regular manner on past history. As such, they provide a more succinct and understandable model of the dynamics and reward function. Existing algorithms for learning RDPs attempt to learn an automaton that reflects the regularity of the underlying domain. However, their scalability is limited due to the practical difficulty of learning automata. In this paper we propose to leverage the power of Deep reinforcement learning in partially observable domain to learn RDPs: First, we learn an RNN-based policy. Then, we generate an automaton that reflects the policy’s structure and use our old data to transform it into an MDP, which we solve. This results in a finite, explainable policy structure, and, as our empirical evaluation on old and new RDP benchmarks shows, much better sample complexity.

AAAI Conference 2021 Conference Paper

Improved Knowledge Modeling and Its Use for Signaling in Multi-Agent Planning with Partial Observability

• Shashank Shekhar
• Ronen I. Brafman
• Guy Shani

Collaborative Multi-Agent Planning (MAP) problems with uncertainty and partial observability are often modeled as Dec-POMDPs. Yet, in deterministic domains, Qualitative Dec-POMDPs can scale up to much larger problem sizes. The best current QDec solver (QDec-FP) reduces MAP problems to multiple single-agent problems. In this paper we describe a planner that uses richer information about agents’ knowledge to improve upon QDec-FP. With this change, the planner not only scales up to larger problems with more objects, but it can also support signaling, where agents signal information to each other by changing the state of the world.

ICAPS Conference 2021 Conference Paper

Verifying Plans and Scripts for Robotics Tasks Using Performance Level Profiles

• Alexander Kovalchuk
• Shashank Shekhar 0002
• Ronen I. Brafman

Performance-Level Profiles (PLPs) were introduced as a type of action representation language suitable for capturing the behavior of functional code for robotics. This paper addresses two issues that PLPs raise: (1) Their formal semantics. (2) How to verify a script or a plan that schedule the use of components that have been documented by PLPs. We provide a formal semantics for PLPs by mapping them to probabilistic timed automata (PTAs). We also show how, given a script that refers to components specified using PLPs, we derive a PTA specification of the entire system. This PTA can be used to verify the system’s properties and answers queries about its behavior. Finally, we empirically evaluate an implemented system based on these ideas, demonstrating its scalability. The result is a pragmatic approach for verifying component-based robotic systems.

IJCAI Conference 2020 Conference Paper

Learning and Solving Regular Decision Processes

• Eden Abadi
• Ronen I. Brafman

Regular Decision Processes (RDPs) are a recently introduced model that extends MDPs with non-Markovian dynamics and rewards. The non-Markovian behavior is restricted to depend on regular properties of the history. These can be specified using regular expressions or formulas in linear dynamic logic over finite traces. Fully specified RDPs can be solved by compiling them into an appropriate MDP. Learning RDPs from data is a challenging problem that has yet to be addressed, on which we focus in this paper. Our approach rests on a new representation for RDPs using Mealy Machines that emit a distribution and an expected reward for each state-action pair. Building on this representation, we combine automata learning techniques with history clustering to learn such a Mealy machine and solve it by adapting MCTS to it. We empirically evaluate this approach, demonstrating its feasibility.

AIJ Journal 2020 Journal Article

Representing and planning with interacting actions and privacy

• Shashank Shekhar
• Ronen I. Brafman

Interacting actions – actions whose joint effect differs from the union of their individual effects – are challenging both to represent and to plan with due to their combinatorial nature. So far, there have been few attempts to provide a succinct language for representing them that can also support efficient centralized planning and distributed privacy preserving planning. In this paper we suggest an approach for representing interacting actions succinctly and show how such a domain model can be compiled into a standard single-agent planning problem as well as to privacy preserving multi-agent planning. We test the performance of our method on a number of novel domains involving interacting actions and privacy.

ICAPS Conference 2019 Conference Paper

A Factored Approach to Deterministic Contingent Multi-Agent Planning

• Shashank Shekhar 0002
• Ronen I. Brafman
• Guy Shani

Collaborative Multi-Agent Planning (MAP) under uncertainty with partial observability is a notoriously difficult problem. Such MAP problems are often modeled as DecPOMDPs, or its qualitative variant, QDec-POMDP, which is essentially a MAP version of contingent planning. The QDecPOMDP model was introduced with the hope that its simpler, non-probabilistic structure will allow for better scalability. Indeed, at least with deterministic actions, the recent IMAP algorithm scales much better than comparable DecPOMDP algorithms (Bazinin and Shani 2018). In this work we suggest a new approach to solving Deterministic QDecPOMDPs based on problem factoring. First, we find a solution to a MAP problem where the results of any observation is available to all agents. This is essentially a single-agent planning problem for the entire team. Then, we project the solution tree into sub-trees, one per agent, and let each agent transform its projected tree into a legal local tree. If all agents succeed, we combine the trees into a valid joint-plan. Otherwise, we continue to explore the space of team solutions. This approach is sound, complete, and as our empirical evaluation demonstrates, scales much better than the IMAP algorithm.

IJCAI Conference 2019 Conference Paper

Planning for LTLf /LDLf Goals in Non-Markovian Fully Observable Nondeterministic Domains

• Ronen I. Brafman
• Giuseppe De Giacomo

In this paper, we investigate non-Markovian Nondeterministic Fully Observable Planning Domains (NMFONDs), variants of Nondeterministic Fully Observable Planning Domains (FONDs) where the next state is determined by the full history leading to the current state. In particular, we introduce TFONDs which are NMFONDs where conditions on the history are succinctly and declaratively specified using the linear-time temporal logic on finite traces LTLf and its extension LDLf. We provide algorithms for planning in TFONDs for general LTLf/LDLf goals, and establish tight complexity bounds w. r. t. the domain representation and the goal, separately. We also show that TFONDs are able to capture all NMFONDs in which the dependency on the history is "finite state". Finally, we show that TFONDs also capture Partially Observable Nondeterministic Planning Domains (PONDs), but without referring to unobservable variables.

IJCAI Conference 2019 Conference Paper

Regular Decision Processes: A Model for Non-Markovian Domains

• Ronen I. Brafman
• Giuseppe De Giacomo

We introduce and study Regular Decision Processes (RDPs), a new, compact, factored model for domains with non-Markovian dynamics and rewards. In RDPs, transition and reward functions are specified using formulas in linear dynamic logic over finite traces, a language with the expressive power of regular expressions. This allows specifying complex dependence on the past using intuitive and compact formulas, and provides a model that generalizes MDPs and k-order MDPs. RDPs can also approximate POMDPs without having to postulate the existence of hidden variables, and, in principle, can be learned from observations only.

AAMAS Conference 2019 Conference Paper

Regular Decision Processes: Modelling Dynamic Systems without Using Hidden Variables: Extended Abstrac

• Ronen I. Brafman
• Giuseppe De Giacomo

We describe Regular Decision Processes (RDPs) a model in between MDPs and POMDPs. Like in POMDPs, the effect of an action may depend on the entire history of actions and observations, but this dependence is restricted to regular functions only. This makes RDP a tractable, yet rich model, that does not hypothesize hidden state, and could possibly be useful for learning dynamic systems.

JAAMAS Journal 2018 Journal Article

Landmark-based heuristic online contingent planning

• Shlomi Maliah
• Guy Shani
• Ronen I. Brafman

Abstract In contingent planning problems, agents have partial information about their state and use sensing actions to learn the value of some variables. When sensing and actuation are separated, plans for such problems can often be viewed as a tree of sensing actions, separated by conformant plans consisting of non-sensing actions that enable the execution of the next sensing action. We propose a heuristic, online method for contingent planning which focuses on identifying the next useful sensing action. We select the next sensing action based on a landmark heuristic, adapted from classical planning. We discuss landmarks for plan trees, providing several alternative definitions and discussing their merits. The key part of our planner is the novel landmarks-based heuristic, together with a projection method that uses classical planning to solve the intermediate conformant planning problems. The resulting heuristic contingent planner solves many more problems than state-of-the-art, translation-based online contingent planners, and in most cases, much faster, up to 3 times faster on simple problems, and 200 times faster on non-simple domains.

ICAPS Conference 2018 Conference Paper

Representing and Planning with Interacting Actions and Privacy

• Shashank Shekhar 0002
• Ronen I. Brafman

Interacting actions — actions whose joint effect differs from the union of their individual effects — are challenging both to represent and to plan with due to their combinatorial nature. So far, there have been few attempts to provide a succinct language for representing them that can also support efficient centralized and distributed privacy preserving planning. In this paper we suggest an approach for representing interacting actions succinctly and show how such a domain model can be compiled into a standard single-agent planning problem as well as to privacy preserving multi-agent planning. We test the performance of our method on a number of novel domains involving interacting actions and privacy.

ICAPS Conference 2017 Conference Paper

Increased Privacy with Reduced Communication in Multi-Agent Planning

• Shlomi Maliah
• Ronen I. Brafman
• Guy Shani

Multi-agent forward search (MAFS) is a state-of-the-art privacy-preserving planning algorithm. We describe a new variant of MAFS, called multi-agent forward-backward search (MAFBS) that uses both forward and backward messages to reduce the number of messages sent and obtain new privacy properties. While MAFS requires agents to send a state s produced by an action a to all agents that can apply any action in s, MAFBS sends such messages forward only to agents that have an action that requires one of the effects of a. To achieve completeness, it sends messages backward to agents that can supply a missing precondition. This more focused message passing scheme reduces states exchanged, and requires that agents be aware only of other agents that they directly interact with, leading to agent privacy.

AIJ Journal 2016 Journal Article

Online belief tracking using regression for contingent planning

• Ronen I. Brafman
• Guy Shani

In online contingent planning under partial observability an agent decides at each time step on the next action to execute, given its initial knowledge of the world, the actions executed so far, and the observation made. Such agents require some representation of their belief state to determine which actions are valid, or whether the goal has been achieved. Efficient maintenance of a belief state is, given its potential exponential size, a key research challenge in this area. In this paper we develop the theory of regression as a useful tool for belief-state maintenance. We provide a formal description of regression, discussing various alternatives and optimization techniques, and analyze its space and time complexity. In particular, we show that, with some care, the regressed formula will contain variables relevant to the current query only, rather than all variables in the problem description. Consequently, under suitable assumptions, the complexity of regression queries is at most exponential in its contextual width. This parameter is always upper bounded by Bonet and Geffner's width parameter, introduced in their state-of-the-art factored belief tracking (FBT) method. In addition, we show how to obtain a poly-sized circuit representation for the online regression formula even with non-deterministic actions. We provide an empirical comparison of regression with FBT-based belief maintenance, showing the power of regression for online belief tracking. We also suggest caching techniques for regression, and demonstrate their value in reducing runtime in current benchmarks.

ICAPS Conference 2016 Conference Paper

Online Macro Generation for Privacy Preserving Planning

• Shlomi Maliah
• Guy Shani
• Ronen I. Brafman

Agents that use Multi-Agent Forward Search (MAFS) todo privacy-preserving planning, often repeatedly develop similar paths. We describe a simple technique for online macro generation allowing agents to reuse successful previous action sequences. By focusing on specific sequences that end with a single public action only, we are able to address the utility problem -- our technique has negligible cost, yet provides both speedups and reduced communication in domains where agents have a reasonable amount of private actions. We describe two variants of our approach, both with attractive privacy preserving properties, and demonstrate the value of macros empirically. We also show that one variant is equivalent to secure MAFS.

IROS Conference 2016 Conference Paper

Performance level profiles: A formal language for describing the expected performance of functional modules

• Ronen I. Brafman
• Michael Bar-Sinai
• Maor Ashkenazi

Despite the existence of powerful formal languages for writing robot controllers, most existing functional modules are written using standard programming languages. The existence of such a code base raises critical challenges: 1. How to enable automated analysis, monitoring, and reuse of existing code given that reasoning directly about code fragments is impractical. 2. How to convey to users the expected level of performance of an autonomous robot? 3. Perhaps most crucial: how to quickly identify abnormal behavior of autonomous robots? This is a key impediment to the deployment of such platforms in open environments. We address these issues through the use of performance-level profiles (PLPs), a formal, yet intuitive, language for specifying the expected properties of functional modules, designed with the above aims in mind. PLPs are motivated by action specification languages, such as PDDL 2. 1, but add novel elements important for robotic applications, such as update frequency, run-time statistics, progress measures, and trigger conditions, and take into account the different roles modules can play. PLPs have been used to support monitoring in two projects: an autonomous compact track loader, and a service robot. Additionally, we developed a number of tools for automated monitoring-code generation from PLPs.

ICAPS Conference 2015 Conference Paper

A Compilation Based Approach to Conformant Probabilistic Planning with Stochastic Actions

• Ran Taig
• Ronen I. Brafman

We extend RBPP, the state-of-the-art, translation-based planner for conformant probabilistic planning (CPP) with deterministic actions, to handle a wide set of CPPs with stochastic actions. Our planner uses relevance analysis to divide a probabilistic "failure-allowance" between the initial state and the stochastic actions. Using its "initial-state allowance, " it uses relevance analysis to select a subset of the set of initial states on which planning efforts will focus. Then, it generates a deterministic planning problem using all-outcome determinization in which action cost reflects the probability of the modeledoutcome. Finally, a cost-bounded classical planner generates a plan with failure probability lower than the"stochastic-effect allowance. " Our compilation method is sound, but incomplete, as it may underestimates the success probability of a plan. Yet, it scales up much better than the state-of-the-art PFF planner, solving larger problems and handling tighter probabilistic bounds on existing benchmarks.

ECAI Conference 2014 Conference Paper

On The Properties of Belief Tracking for Online Contingent Planning using Regression

• Ronen I. Brafman
• Guy Shani

Planning under partial observability typically requires some representation of the agent's belief state - either online to determine which actions are valid, or offline for planning. Due to its potential exponential size, efficient maintenance of a belief state is, thus, a key research challenge in this area. The state-of-the-art factored belief tracking (FBT) method addresses this problem by maintaining multiple smaller projected belief states, each involving only a subset of the variable set. Its complexity is exponential in the size of these subsets, as opposed to the entire variable set, without jeopardizing completeness. In this paper we develop the theory of regression to serve as an alternative tool for belief-state maintenance. Regression is a well known technique enjoying similar, and potentially even better worst-case complexity, as its complexity depends on the actions and observations that actually took place, rather than all actions and potential observations, as in the FBT method. On the other hand, FBT is likely to have better amortized complexity if the number of queries to the belief state is very large. An empirical comparison of regression with FBT-based belief maintenance is carried out, showing that the two perform similarly.

ICAPS Conference 2014 Conference Paper

Partially Observable Online Contingent Planning Using Landmark Heuristics

• Shlomi Maliah
• Ronen I. Brafman
• Erez Karpas
• Guy Shani

In contingent planning problems, agents have partial information about their state anduse sensing actions to learn the value of some variables. When sensing and actuation are separated, plans for such problems can often be viewed as a tree of sensing actions, separated by conformant plans consisting of non-sensing actions that enable the execution of the next sensing action. This leads us to propose a heuristic, online method for contingent planning which focuses on identifying thenext useful sensing action. The key part of our planner is a novel landmarks-based heuristic for selecting the next sensing action, together with a projection method that uses classical planning to solve the intermediate conformant planning problems. This allows our planner to operate without an explicit model of belief space or the use of existing translation techniques, both of which can require exponential space. The resulting Heuristic Contingent Planner (HCP) solves many more problems than state-of-the-art, translation-based online contingent planners, and in most cases much faster.

ICAPS Conference 2013 Conference Paper

Compiling Conformant Probabilistic Planning Problems into Classical Planning

• Ran Taig
• Ronen I. Brafman

In CPP, we are given a set of actions (assumed deterministic in this paper), a distribution over initial states, a goal condition, and a real value 0 < θ ≤1. We seek a plan π such that following its execution, the goal probability is at least θ. Motivated by the success of the translation-based approach for conformant planning, introduced by Palacios and Geffner, we suggest a new compilation scheme from CPP to classical planning. Our compilation scheme maps CPP into cost-bounded classical planning, where the cost-bound represents the maximum allowed probability of failure. Empirically, this technique shows mixed, but promising results, performing very well on some domains, and less so on others when compared to the state of the art PFF planner. It is also very flexible due to its generic nature, allowing us to experiment with diverse search strategies developed for classical planning. Our results show that compilation-based technique offer a new viable approach to CPP and, possibly, more general probabilistic planning problems.

AIJ Journal 2013 Journal Article

On the complexity of planning for agent teams and its implications for single agent planning

• Ronen I. Brafman
• Carmel Domshlak

If the complexity of planning for a single agent is described by some function f of the input, how much more difficult is it to plan for a team of n cooperating agents? If these agents are completely independent, we can simply solve n single agent problems, scaling linearly with the number of agents. But if all the agents interact tightly, we really need to solve a single problem that is n times larger, which could be exponentially (in n) harder to solve. Is a more general characterization possible? To formulate this question precisely, we minimally extend the standard STRIPS model to describe multi-agent planning problems. Then, we identify two problem parameters that help us answer our question. The first parameter is independent of the precise task the multi-agent system should plan for, and it captures the structure of the possible direct interactions between the agents via the tree-width of a graph induced by the team. The second parameter is task-dependent, and it captures the minimal number of interactions by the “most interacting” agent in the team that is needed to solve the problem. We show that multi-agent planning problems can be solved in time exponential only in these parameters. Thus, when these parameters are bounded, the complexity scales only polynomially in the size of the agent team. These results also have direct implications for the single-agent case: by casting single-agent planning tasks as multi-agent planning tasks, we can devise novel methods for decomposition-based planning for single agents. We analyze one such method, and use the techniques developed to provide some of the strongest tractability results for classical single-agent planning to date.

UAI Conference 2012 Conference Paper

Exploiting Uniform Assignments in First-Order MPE

• Udi Apsel
• Ronen I. Brafman

The MPE (Most Probable Explanation) query plays an important role in probabilistic inference. MPE solution algorithms for probabilistic relational models essentially adapt existing belief assessment method, replacing summation with maximization. But the rich structure and symmetries captured by relational models together with the properties of the maximization operator offer an opportunity for additional simplification with potentially significant computational ramifications. Specifically, these models often have groups of variables that define symmetric distributions over some population of formulas. The maximizing choice for different elements of this group is the same. If we can realize this ahead of time, we can significantly reduce the size of the model by eliminating a potentially significant portion of random variables. This paper defines the notion of uniformly assigned and partially uniformly assigned sets of variables, shows how one can recognize these sets efficiently, and how the model can be greatly simplified once we recognize them, with little computational effort. We demonstrate the effectiveness of these ideas empirically on a number of models.

ICAPS Conference 2012 Conference Paper

Pruning Methods for Optimal Delete-Free Planning

• Avitan Gefen
• Ronen I. Brafman

Delete-free planning underlies many popular relaxation (h+) based heuristics used in state-of-the-art planners; it provides a simpler setting for exploring new pruning methods and other ideas; and a number of interesting recent planning domains are naturally delete-free. In this paper we explore new pruning methods for planning in delete-free planning domains. First, we observe that optimal delete-free plans can be composed from contiguous sub-plans that focus on one fact landmark at a time. Thus, instead of attempting to achieve the goal, the planner can focus on more easily achievable landmarks at each stage. Then, we suggest a number of complementary pruning techniques that are made more powerful with this observation. To carry out these pruning techniques efficiently, we make heavy use of an And/Or graph depicting the planning problem. We empirically evaluate these ideas using the FD framework, and show that they lead to clear improvements.

ECAI Conference 2012 Conference Paper

Tunneling and Decomposition-Based State Reduction for Optimal Planning

• Raz Nissim
• Udi Apsel
• Ronen I. Brafman

Action pruning is one of the most basic techniques for improving a planner's performance. The challenge of preserving optimality while reducing the state space has been addressed by several methods in recent years. In this paper we describe two optimality preserving pruning methods: The first is a generalization of tunnel macros. The second, the main contribution of this paper, is a novel partition-based pruning method. The latter requires the introduction of new automated domain decomposition techniques which are of independent interest. Both methods prune the actions applicable at state s based on the last action leading to s, and both attempt to capture the intuition that, when possible, we should focus on one subgoal at a time. As we demonstrate, neither method dominates the other, and a combination of both allows us to obtain an even stronger pruning rule. We also introduce a few modifications to A* that utilize properties shared by both methods to find an optimal plan. Our empirical evaluation compares the pruning power of the two methods and their combination, showing good coverage, reduction in running time, and reduction in the number of expansions.

UAI Conference 2011 Conference Paper

Extended Lifted Inference with Joint Formulas

• Udi Apsel
• Ronen I. Brafman

AIJ Journal 2011 Journal Article

Relational preference rules for control

• Ronen I. Brafman

Value functions are defined over a fixed set of outcomes. In work on preference handling in AI, these outcomes are usually a set of assignments over a fixed set of state variables. If the set of variables changes, a new value function must be elicited. Given that in most applications the state variables are properties (attributes) of objects in the world, this implies that the introduction of new objects requires re-elicitation of preferences. However, often, the user has in mind preferential information that is much more generic, and which is relevant to a given type of domain regardless of the precise number of objects of each kind and their properties. Such information requires the introduction of relational models. Following in the footsteps of work on probabilistic relational models (PRMs), we suggest in this work a rule-based, relational language of preferences. This language extends regular rule-based languages and leads to a much more flexible approach for specifying control rules for autonomous systems. It also extends standard generalized-additive value functions to handle a dynamic universe of objects. Given any specific set of objects this specification induces a generalized-additive value function over assignments to the controllable attributes associated with these objects. We then describe a prototype of a decision support system for command and control centers we developed to illustrate and study the use of these rules.

IJCAI Conference 2011 Conference Paper

Replanning in Domains with Partial Information and Sensing Actions

• Guy Shani
• Ronen I. Brafman

Replanning via determinization is a recent, popular approach for onlineplanning in MDPs. In this paper we adapt this idea to classical, non-stochastic domains with partial information and sensing actions. At eachstep we generate a candidate plan which solves a classical planning probleminduced by the original problem. We execute this plan as long as it is safeto do so. When this is no longer the case, we replan. The classical planning problem we generate is based on the T0 translation, in which the classical state captures the knowledge state of theagent. We overcome the non-determinism in sensing actions, and the large domain size introduced by T0 by using state sampling. Our planner also employs a novel, lazy, regression-based method for querying the belief state.

ICAPS Conference 2011 Conference Paper

The Minimal Seed Set Problem

• Avitan Gefen
• Ronen I. Brafman

This paper defines and studies a new, interesting, and challenging benchmark problem that originates in systems biology. The minimal seed-set problem is defined as follows: given a description of the metabolic reactions of an organism, characterize the minimal set of nutrients with which it could synthesize all nutrients it is capable of synthesizing. Current methods used in systems biology yield only approximate solutions. And although it is natural to cast it as a planning problem, current optimal planners are unable to solve it, while non-optimal planners return plans that are very far from optimal. As a planning problem, it is inherently delete-free, has many zero-cost actions, all propositions are landmarks, and many legal permutations of the plan exist. We show how a simple uninformed search algorithm that exploits inherent independence between sub-goals can solve it optimally by reducing the branching factor drastically.

IJCAI Conference 2009 Conference Paper

• Ronen I. Brafman
• Carmel Domshlak
• Yagil Engel
• Moshe Tennenholtz

We introduce planning games, a study of interactions of self-motivated agents in automated planning settings. Planning games extend STRIPS-like models of single-agent planning to systems of multiple self-interested agents, providing a rich class of structured games that capture subtle forms of local interactions. We consider two basic models of planning games and adapt game-theoretic solution concepts to these models. In both models, agents may need to cooperate in order to achieve their goals, but are assumed to do so only in order to increase their net benefit. For each model we study the computational problem of finding a stable solution and provide efficient algorithms for systems exhibiting acyclic interaction structure.

ICAPS Conference 2008 Conference Paper

Efficient ADD Operations for Point-Based Algorithms

• Guy Shani
• Pascal Poupart
• Ronen I. Brafman
• Solomon Eyal Shimony

During the past few years, point-based POMDP solvers have gradually scaled up to handle medium sized domains through better selection of the set of points and efficient backup methods. Point-based research has focused on flat, explicit representation of the state space, yet in many realistic domains a factored representation is more appropriate. The latter have exponentially large state-spaces, and current methods are unlikely to handle models of reasonable size. Thus, adapting point-based methods to factored representations by modeling propositional state spaces better, e. g. by using Algebraic Decision Diagrams (ADDs) is needed. While a straightforward ADD-based implementation can effectively tackle large factored POMDPs, we propose several techniques to further improve scalability. In particular, we show how ADDs can be used successfully in factored domains that exhibit reasonable locality. Our algorithms are several orders of magnitude faster than current point-based algorithms used with flat representations.

ICAPS Conference 2008 Conference Paper

From One to Many: Planning for Loosely Coupled Multi-Agent Systems

• Ronen I. Brafman
• Carmel Domshlak

Loosely coupled multi-agent systems are perceived as easier to plan for because they require less coordination between agent sub-plans. In this paper we set out to formalize this intuition. We establish an upper bound on the complexity of multi-agent planning problems that depends exponentially on two parameters quantifying the level of agents' coupling, and on these parameters only. The first parameter is problem-independent, and it measures the inherent level of coupling within the system. The second is problem-specific and it has to do with the minmax number of action-commitments per agent required to solve the problem. Most importantly, the direct dependence on the number of agents, on the overall size of the problem, and on the length of the agents' plans, is only polynomial. This result is obtained using a new algorithmic methodology which we call "planning as CSP+planning". We believe this to be one of the first formal results to both quantify the notion of agents' coupling, and to demonstrate a multi-agent planning algorithm that, for fixed coupling levels, scales polynomially with the size of the problem.

AIJ Journal 2008 Journal Article

Graphically structured value-function compilation

• Ronen I. Brafman
• Carmel Domshlak

Classical work on eliciting and representing preferences over multi-attribute alternatives has attempted to recognize conditions under which value functions take on particularly simple and compact form, making their elicitation much easier. In this paper we consider preferences over discrete domains, and show that for a certain class of simple and intuitive qualitative preference statements, one can always generate compact value functions consistent with these statements. These value functions maintain the independence structure implicit in the original statements. For discrete domains, these representation theorems are much more general than previous results. However, we also show that it is not always possible to maintain this compact structure if we add explicit ordering constraints among the available outcomes.

JMLR Journal 2008 Journal Article

Multi-Agent Reinforcement Learning in Common Interest and Fixed Sum Stochastic Games: An Experimental Study

• Avraham Bab
• Ronen I. Brafman

Multi Agent Reinforcement Learning (MARL) has received continually growing attention in the past decade. Many algorithms that vary in their approaches to the different subtasks of MARL have been developed. However, the theoretical convergence results for these algorithms do not give a clue as to their practical performance nor supply insights to the dynamics of the learning process itself. This work is a comprehensive empirical study conducted on MGS, a simulation system developed for this purpose. It surveys the important algorithms in the field, demonstrates the strengths and weaknesses of the different approaches to MARL through application of FriendQ, OAL, WoLF, FoeQ, Rmax, and other algorithms to a variety of fully cooperative and fully competitive domains in self and heterogeneous play, and supplies an informal analysis of the resulting learning processes. The results can aid in the design of new learning algorithms, in matching existing algorithms to specific tasks, and may guide further research and formal analysis of the learning processes. [abs] [ pdf ][ bib ] &copy JMLR 2008. ( edit, beta )

KR Conference 2008 Conference Paper

Relational Preference Rules for Control

• Ronen I. Brafman

Much like relational probabilistic models, the need for relational preference models arises naturally in real-world applications where the set of object classes is fixed, but object instances vary from one application to another as well as within the run-time of a single application. To address this problem, we suggest a rule-based preference specification language. This language extends regular rule-based languages and leads to a much more flexible approach for specifying control rules for autonomous systems. It also extends standard generalized-additive value functions to handle a dynamic universe of objects: given any specific set of objects it induces a generalized-additive value function. Throughout the paper we use the example of a decision support system for command and control centers we are currently developing to motivate the need for such models and to illustrate them.

IJCAI Conference 2007 Conference Paper

• Guy Shani
• Ronen I. Brafman
• Solomon E. Shimony

Recent scaling up of POMDP solvers towards realistic applications is largely due to point-based methods which quickly converge to an approximate solution for medium-sized problems. Of this family HSVI, which uses trial-based asynchronous value iteration, can handle the largest domains. In this paper we suggest a new algorithm, FSVI, that uses the underlying MDP to traverse the belief space towards rewards, finding sequences of useful backups, and show how it scales up better than HSVI on larger benchmarks.

AIJ Journal 2006 Journal Article

Conformant planning via heuristic forward search: A new approach

• Jörg Hoffmann
• Ronen I. Brafman

Conformant planning is the task of generating plans given uncertainty about the initial state and action effects, and without any sensing capabilities during plan execution. The plan should be successful regardless of which particular initial world we start from. It is well known that conformant planning can be transformed into a search problem in belief space, the space whose elements are sets of possible worlds. We introduce a new representation of that search space, replacing the need to store sets of possible worlds with a need to reason about the effects of action sequences. The reasoning is done by implication tests on propositional formulas in conjunctive normal form (CNF) that capture the action sequence semantics. Based on this approach, we extend the classical heuristic forward-search planning system FF to the conformant setting. The key to this extension is an appropriate extension of the relaxation that underlies FF's heuristic function, and of FF's machinery for solving relaxed planning problems: the extended machinery includes a stronger form of the CNF implication tests that we use to reason about the effects of action sequences. Our experimental evaluation shows the resulting planning system to be superior to the state-of-the-art conformant planners MBP, KACMBP, and GPT in a variety of benchmark domains.

AAAI Conference 2006 Conference Paper

Factored Planning: How, When, and When Not

• Ronen I. Brafman

Automated domain factoring, and planning methods that utilize them, have long been of interest to planning researchers. Recent work in this area yielded new theoretical insight and algorithms, but left many questions open: How to decompose a domain into factors? How to work with these factors? And whether and when decomposition-based methods are useful? This paper provides theoretical analysis that answers many of these questions: it proposes a novel approach to factored planning; proves its theoretical superiority over previous methods; provides insight into how to factor domains; and uses its novel complexity results to analyze when factored planning is likely to perform well, and when not. It also establishes the key role played by the domain’s causal graph in the complexity analysis of planning algorithms.

AAAI Conference 2006 Conference Paper

Preferences over Sets

• Ronen I. Brafman
• Solomon E. Shimony

Research on preference elicitation and reasoning typically focuses on preferences over single objects of interest. However, in a number of applications the “outcomes” of interest are sets of such atomic objects. For instance, when creating the program for a film festival, editing a newspaper, or putting together a team, we need to select a set of films (resp. articles, members) that is optimal with respect to quality, diversity, cohesiveness, etc. This paper describes an intuitive approach for specifying preferences over sets of objects. An algorithm for computing an optimal subset, given a set of candidate objects and a preference specification, is developed and evaluated.

ICAPS Conference 2006 Conference Paper

Stochastic Over-Subscription Planning Using Hierarchies of MDPs

• Nicolas Meuleau
• Ronen I. Brafman
• Emmanuel Benazera

In over-subscription planning (OSP), the set of goals is not achievable jointly, and the task is to find a plan that attains the best feasible subset of goals given resource constraints. Recent classical OSP algorithms ignore the uncertainty inherent in many natural application domains where OSPs arise. And while modeling stochastic OSP problems as MDPs is easy, the resulting models are too large for standard solution approaches. Fortunately OSP problems have a natural two-tiered hierarchy, and in this paper we adapt and extend tools developed in the hierarchical reinforcement learning community in order to effectively exploit this hierarchy and obtain compact, factored policies. Typically, such policies are sub-optimal, but under certain assumptions that hold in our planetary exploration domain, our factored solution is, in fact, optimal. Our algorithms work by repeatedly solving a number of smaller MDPs, while propagating information between them. We evaluate a number of variants of this approach on a set of stochastic instances of a planetary rover domain, showing substantial performance gains.

ICAPS Conference 2006 Conference Paper

Tractable Optimal Competitive Scheduling

• Jeremy Frank
• James Crawford
• Lina Khatib
• Ronen I. Brafman

In this paper we describe the problem of Optimal Competitive Scheduling, which consists of activities that compete for a shared resource. The objective is to choose a subset of activities to schedule, sequence them, and decide how much time they are allowed, in such a way that temporal and resource constraints are satisfied and overall schedule quality is maximized. While most such problems are NP-complete, very restricted versions of this problem are known to be tractable. In this work we describe tractable variations on this problem that correspond to realistic scheduling problems. The first class of tractable OCS problems arises due to limitations on the objective function that permit casting the problem as a Linear Program; with one additional assumption on activity feasibility windows, we identify a problem class where an optimal activity ordering can be found in polynomial time. The second class arises by reformulation of the problem as a Valued Constraint Satisfaction Problem and exploiting known results on tractability. We describe implementations of special-purpose algorithms designed to solve tractable OCS problems, and identify different solver performance characteristics based on properties of the problem instances.

JMLR Journal 2005 Journal Article

An MDP-Based Recommender System

• Guy Shani
• David Heckerman
• Ronen I. Brafman

Typical recommender systems adopt a static view of the recommendation process and treat it as a prediction problem. We argue that it is more appropriate to view the problem of generating recommendations as a sequential optimization problem and, consequently, that Markov decision processes (MDPs) provide a more appropriate model for recommender systems. MDPs introduce two benefits: they take into account the long-term effects of each recommendation and the expected value of each recommendation. To succeed in practice, an MDP-based recommender system must employ a strong initial model, must be solvable quickly, and should not consume too much memory. In this paper, we describe our particular MDP model, its initialization using a predictive model, the solution and update algorithm, and its actual performance on a commercial site. We also describe the particular predictive model we used which outperforms previous models. Our system is one of a small number of commercially deployed recommender systems. As far as we know, it is the first to report experimental analysis conducted on a real commercial site. These results validate the commercial value of recommender systems, and in particular, of our MDP-based approach. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

ICAPS Conference 2005 Conference Paper

Contingent Planning via Heuristic Forward Search witn Implicit Belief States

• Jörg Hoffmann 0001
• Ronen I. Brafman

Contingent planning is the task of generating a conditional plan given uncertainty about the initial state and action effects, but with the ability to observe some aspects of the current world state. Contingent planning can be transformed into an And-Or search problem in belief space, the space whose elements are sets of possible worlds. In Brafman and Hoffmann (2004), we introduced a method for implicitly representing a belief state using a propositional formula that describes the sequence of actions leading to that state. This representation trades off space for time and was shown to be quite effective for conformant planning within a heuristic forward-search planner based on the FF system. In this paper we apply the same architecture to contingent planning. The changes required to adapt the search space representation are small. More effort is required to adapt the relaxed planning problems whose solution informs the forward search algorithm. We propose the targeted use of an additional relaxation, mapping the relaxed contingent problem into a relaxed conformant problem. Experimental results show that the resulting planning system, Contingent-FF, is highly competitive with the state-of-the-art contingent planners POND and MBP.

ICAPS Conference 2005 Conference Paper

Planning with Goal Preferences and Constraints

• Ronen I. Brafman
• Yuri Chernyavsky

Contingent planning is the task of generating a conditional plan given uncertainty about the initial state and action effects, but with the ability to observe some aspects of the current world state. Contingent planning can be transformed into an And-Or search problem in belief space, the space whose elements are sets of possible worlds. In Brafman and Hoffmann (2004), we introduced a method for implicitly representing a belief state using a propositional formula that describes the sequence of actions leading to that state. This representation trades off space for time and was shown to be quite effective for conformant planning within a heuristic forward-search planner based on the FF system. In this paper we apply the same architecture to contingent planning. The changes required to adapt the search space representation are small. More effort is required to adapt the relaxed planning problems whose solution informs the forward search algorithm. We propose the targeted use of an additional relaxation, mapping the relaxed contingent problem into a relaxed conformant problem. Experimental results show that the resulting planning system, Contingent-FF, is highly competitive with the state-of-the-art contingent planners POND and MBP.

UAI Conference 2004 Conference Paper

Compact Value-Function Representations for Qualitative Preferences

• Ronen I. Brafman
• Carmel Domshlak
• Tanya Kogan

We consider the challenge of preference elicitation in systems that help users discover the most desirable item(s) within a given database. Past work on preference elicitation focused on structured models that provide a factored representation of users' preferences. Such models require less information to construct and support efficient reasoning algorithms. This paper makes two substantial contributions to this area: (1) Strong representation theorems for factored value functions. (2) A methodology that utilizes our representation results to address the problem of optimal item selection.

ICAPS Conference 2004 Conference Paper

Conformant Planning via Heuristic Forward Search: A New Approach

• Ronen I. Brafman
• Jörg Hoffmann 0001

Conformant planning is the task of generating plans given uncertainty about the initial state and action effects, and without any sensing capabilities during plan execution. The plan should be successful regardless of which particular initial world we start from. It is well known that conformant planning can be transformed into a search problem in belief space, the space whose elements are sets of possible worlds. We introduce a new representation of that search space, replacing the need to store sets of possible worlds with a need to reason about the effects of action sequences. The reasoning is done by deciding solvability of CNFs that capture the action sequence’s semantics. Based on this approach, we extend the classical heuristic planning system FF to the conformant setting. The key to this extension is the introduction of approximative CNF reasoning in FF’s heuristic function. Our experimental evaluation shows Conformant-FF to be superior to the state-of-the-art conformant planners MBP, KACMBP, and GPT in a variety of benchmark domains.

AIJ Journal 2004 Journal Article

Efficient learning equilibrium

• Ronen I. Brafman
• Moshe Tennenholtz

We introduce efficient learning equilibrium (ELE), a normative approach to learning in non-cooperative settings. In ELE, the learning algorithms themselves are required to be in equilibrium. In addition, the learning algorithms must arrive at a desired value after polynomial time, and a deviation from the prescribed ELE becomes irrational after polynomial time. We prove the existence of an ELE (where the desired value is the expected payoff in a Nash equilibrium) and of a Pareto-ELE (where the objective is the maximization of social surplus) in repeated games with perfect monitoring. We also show that an ELE does not always exist in the imperfect monitoring case. Finally, we discuss the extension of these results to general-sum stochastic games.

IJCAI Conference 2003 Conference Paper

A New Look at the Semantics and Optimization Methods of CP-Networks

• Ronen I. Brafman
• Yannis Dimopoulos

Preference elicitation is a serious bottleneck in many decision support applications and agent specification tasks. CP-nets were designed to make the preference elicitation process simpler and more intuitive for lay users by graphically structuring a set of Ceteris Paribus (CP) preference statements preference statements most people find natural and intuitive. In various contexts, CP-nets with an underlying cyclic structure emerge naturally. Often, they are inconsistent according to the current semantics, and the user is required to revise them. In this paper we show how optimization queries can be meaningfully answered in many "inconsistent" networks without troubling the user with requests for revisions. We also describe a method for focusing users' revision process when revisions are truly needed. In the process, we provide a formal semantics that justifies our approach and we introduce new techniques for computing optimal outcomes.

ICAPS Conference 2003 Conference Paper

Recommendation as a Stochastic Sequential Decision Problem

• Ronen I. Brafman
• David Heckerman
• Guy Shani

Recommender systems -- systems that suggest to users in e-commerce sites items that might interest them -- adopt a static view of the recommendation process and treat it as a prediction problem. In an earlier paper, we argued that it is more appropriate to view the problem of generating recommendations as a sequential decision problem and, consequently, that Markov decision processes (MDPs) provide a more appropriate model for recommender systems. MDPs introduce two benefits: they take into account the long-term effects of each recommendation, and they take into account the expected value of each recommendation. The use of MDPs in a commercial site raises three fundamental problems: providing an adequate initial model, updating this model online as new items (e. g., books) arrive, and coping with the enormous state-space of this model. In past work, we dealt with the first problem. In this paper we consider the second, and especially, the third problem, which is of greater concern to researchers in decision-theoretic planning. We show that although the model we consider has roughly 1011 states, we can quickly provide an approximate solution by utilizing its special structure. Our memory requirements -- a serious concern for commercial online applications -- are modest; and the overall resource requirements of our system are comparable to those of a well-known commercial recommender system that uses a simpler and less accurate model. Our system is one of a handful of deployed commercial recommender systems as well as one of a handful of MDP-based deployed systems. It has been running at www. mitos. co. il, a commercial online bookstore, since August, 2002.

UAI Conference 2002 Conference Paper

An MDP-based Recommender System

• Guy Shani
• Ronen I. Brafman
• David Heckerman

Typical Recommender systems adopt a static view of the recommendation process and treat it as a prediction problem. We argue that it is more appropriate to view the problem of generating recommendations as a sequential decision problem and, consequently, that Markov decision processes (MDP) provide a more appropriate model for Recommender systems. MDPs introduce two benefits: they take into account the long-term effects of each recommendation, and they take into account the expected value of each recommendation. To succeed in practice, an MDP-based Recommender system must employ a strong initial model; and the bulk of this paper is concerned with the generation of such a model. In particular, we suggest the use of an n-gram predictive model for generating the initial MDP. Our n-gram model induces a Markov-chain model of user behavior whose predictive accuracy is greater than that of existing predictive models. We describe our predictive model in detail and evaluate its performance on real data. In addition, we show how the model can be used in an MDP-based Recommender system.

KR Conference 2002 Conference Paper

CP-nets - Reasoning and Consistency Testing

• Carmel Domshlak
• Ronen I. Brafman

UAI Conference 2002 Conference Paper

Introducing Variable Importance Tradeoffs into CP-Nets

• Ronen I. Brafman
• Carmel Domshlak

The ability to make decisions and to assess potential courses of action is a corner-stone of many AI applications, and usually this requires explicit information about the decision-maker s preferences. IN many applications, preference elicitation IS a serious bottleneck.The USER either does NOT have the time, the knowledge, OR the expert support required TO specify complex multi - attribute utility functions. IN such cases, a method that IS based ON intuitive, yet expressive, preference statements IS required. IN this paper we suggest the USE OF TCP - nets, an enhancement OF CP - nets, AS a tool FOR representing, AND reasoning about qualitative preference statements.We present AND motivate this framework, define its semantics, AND show how it can be used TO perform constrained optimization.

JMLR Journal 2002 Journal Article

R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning

• Ronen I. Brafman
• Moshe Tennenholtz

R-MAX is a very simple model-based reinforcement learning algorithm which can attain near-optimal average reward in polynomial time. In R-MAX, the agent always maintains a complete, but possibly inaccurate model of its environment and acts based on the optimal policy derived from this model. The model is initialized in an optimistic fashion: all actions in all states return the maximal possible reward (hence the name). During execution, it is updated based on the agent's observations. R-MAX improves upon several previous algorithms: (1) It is simpler and more general than Kearns and Singh's E^3 algorithm, covering zero-sum stochastic games. (2) It has a built-in mechanism for resolving the exploration vs. exploitation dilemma. (3) It formally justifies the ``optimism under uncertainty'' bias used in many RL algorithms. (4) It is simpler, more general, and more efficient than Brafman and Tennenholtz's LSG algorithm for learning in single controller stochastic games. (5) It generalizes the algorithm by Monderer and Tennenholtz for learning in repeated games. (6) It is the only algorithm for learning in repeated games, to date, which is provably efficient, considerably improving and simplifying previous algorithms by Banos and by Megiddo.

ICAPS Conference 2002 Conference Paper

Structure and Complexity in Planning with Unary Operators

• Carmel Domshlak
• Ronen I. Brafman

Unary operator domains - i. e., domains in which operators have a single effect - arise naturally in many control problems. In its most general form, the problem of STRIPS planning in unary operator domains is known to be as hard as the general STRIPS planning problem - both are PSPACE-complete. However, unary operator domains induce a natural structure, called the domain’s causal graph. This graph relates between the preconditions and effect of each domain operator. Causal graphs were exploited by Williams and Nayak in order to analyze plan generation for one of the controllers in NASA’s Deep-Space One spacecraft. There, they utilized the fact that when this graph is a tree, a serialization ordering over any subgoal can be obtained quickly. In this paper we conduct a comprehensive study of the relationship between the structure of a domain’s causal graph and the complexity of planning in this domain. On the positive side, we show that a non-trivial polynomial time plan generation algorithm exists for domains whose causal graph induces a polytree with a constant bound on its node indegree. On the negative side, we show that even plan existence is hard when the graph is a singly connected DAG. More generally, we show that the number of paths in the causal graph is closely related to the complexity of planning in the associated domain. Finally we relate our results to the question of complexity of planning with serializable subgoals.

AIJ Journal 2001 Journal Article

On decision-theoretic foundations for defaults

• Ronen I. Brafman
• Nir Friedman

In recent years, considerable effort has gone into understanding default reasoning. Most of this effort concentrated on the question of entailment, i. e. , what conclusions are warranted by a knowledge-base of defaults. Surprisingly, few works formally examine the general role of defaults. We argue that an examination of this role is necessary in order to understand defaults, and suggest a concrete role for defaults: Defaults simplify our decision-making process, allowing us to make fast, approximately optimal decisions by ignoring certain possible states. In order to formalize this approach, we examine decision making in the framework of decision theory. We use probability and utility to measure the impact of possible states on the decision-making process. More precisely, we examine when a consequence relation, which is the set of default inferences made by an inference system, can be compatible with such a decision-theoretic setup. We characterize general properties that such consequence relations must satisfy and contrast them with previous analysis of default consequence relations in the literature. In particular, we show that such consequence relations must satisfy the properties of cumulative reasoning. Finally, we compare our approach with Poole's decision-theoretic defaults, and show how both can be combined to form an attractive framework for reasoning about decisions.

UAI Conference 2001 Conference Paper

UCP-Networks: A Directed Graphical Representation of Conditional Utilities

• Craig Boutilier
• Fahiem Bacchus
• Ronen I. Brafman

We propose a new directed graphical representation of utility functions, called UCP-networks, that combines aspects of two existing graphical models: generalized additive models and CP-networks. The network decomposes a utility function into a number of additive factors, with the directionality of the arcs reflecting conditional dependence of preference statements---in the underlying (qualitative) preference ordering---under a {em ceteris paribus} (all else being equal) interpretation. This representation is arguably natural in many settings. Furthermore, the strong CP-semantics ensures that computation of optimization and dominance queries is very efficient. We also demonstrate the value of this representation in decision making. Finally, we describe an interactive elicitation procedure that takes advantage of the linear nature of the constraints on ``tradeoff weights'' imposed by a UCP-network. This procedure allows the network to be refined until the regret of the decision with minimax regret (with respect to the incompletely specified utility function) falls below a specified threshold (e.g., the cost of further questioning.

AIJ Journal 2000 Journal Article

A near-optimal polynomial time algorithm for learning in certain classes of stochastic games

• Ronen I. Brafman
• Moshe Tennenholtz

We present a new algorithm for polynomial time learning of optimal behavior in single-controller stochastic games. This algorithm incorporates and integrates important recent results of Kearns and Singh (Proc. ICML-98, 1998) in reinforcement learning and of Monderer and Tennenholtz (J. Artif. Intell. Res. 7, 1997, p. 231) in repeated games. In stochastic games, the agent must cope with the existence of an adversary whose actions can be arbitrary. In particular, this adversary can withhold information about the game matrix by refraining from (or rarely) performing certain actions. This forces upon us an exploration versus exploitation dilemma more complex than in Markov decision processes in which, given information about particular parts of a game matrix, the agent must decide how much effort to invest in learning the unknown parts of the matrix. We present a polynomial time algorithm that addresses these issues in the context of the class of single controller stochastic games, providing the agent with near-optimal return.

UAI Conference 1999 Conference Paper

Reasoning With Conditional Ceteris Paribus Preference Statements

• Craig Boutilier
• Ronen I. Brafman
• Holger H. Hoos
• David Poole 0001

IJCAI Conference 1999 Conference Paper

To Encode or not to Encode - I: Linear Planning

• Ronen I. Brafman
• Holger H. Hoos

Stochastic local search (SLS) techniques are very effective in solving hard prepositional satisfiability problems. This has lead to the popularity of the en­ code & solve paradigm in which different problems are encoded as propositional satisfiability problems to which SLS techniques are applied. In AI, plan­ ning is the main area in which this methodology is used. Yet, it seems plausible that SLS methods should perform better when applied to the original problem space whose structure they can exploit. As part of our attempts to validate this thesis, we ex­ perimented with LPSP, a planner that applies SLS techniques to the space of linear plans. LPSP out­ performs SLS applied to encoded planning prob­ lems that enforce a similar linearity assumption be­ cause of its ability to exploit the special structure of planning problems. Additional experiments (re­ ported in a longer version of this paper) conducted on the Hamiltonian circuit problem lend farther support to our thesis.

AIJ Journal 1998 Journal Article

On the knowledge requirements of tasks

• Ronen I. Brafman
• Joseph Y. Halpern
• Yoav Shoham

In order to successfully perform a task, a situated system requires some information about its domain. If we can understand what information the system requires, we may be able to equip it with more suitable sensors or make better use of the information available to it. These considerations have motivated roboticists to examine the issue of sensor design, and in particular, the minimal information required to perform a task. We show here that reasoning in terms of what the robot knows and needs to know to perform a task is a useful approach for analyzing these issues. We extend the formal framework for reasoning about knowledge, already used in AI and distributed computing, by developing a set of basic concepts and tools for modeling and analyzing the knowledge requirements of tasks. We investigate properties of the resulting framework, and show how it can be applied to robotics tasks.

UAI Conference 1998 Conference Paper

Structured Reachability Analysis for Markov Decision Processes

• Craig Boutilier
• Ronen I. Brafman
• Christopher W. Geib

AAAI Conference 1997 Conference Paper

A Heuristic Variable Grid Solution Method for POMDPs

• Ronen I. Brafman

Partially observable Markov decision processes (POMDPs) are an appealing tool for modeling planning problems under uncertainty. They incorporate stochastic action and sensor descriptions and easily capture goal oriented and process oriented tasks. Unfortunately, POMDPs are very difficult to solve. Exact methods cannot handle problems with much more than 10 states, so approximate methods must be used. In this paper, we describe a simple variable-grid solution method which yields good results on relatively large problems with modest computational effort.

AIJ Journal 1997 Journal Article

Modeling agents as qualitative decision makers

• Ronen I. Brafman
• Moshe Tennenholtz

We investigate the semantic foundations of a method for modeling agents as entities with a mental state which was suggested by McCarthy and by Newell. Our goals are to formalize this modeling approach and its semantics, to understand the theoretical and practical issues that it raises, and to address some of them. In particular, this requires specifying the model's parameters and how these parameters are to be assigned (i. e. , their grounding). We propose a basic model in which the agent is viewed as a qualitative decision maker with beliefs, preferences, and a decision strategy; and we show how these components would determine the agent's behavior. We ground this model in the agent's interaction with the world, namely, in its actions. This is done by viewing model construction as a constraint satisfaction problem in which we search for a model consistent with the agent's behavior and with our general background knowledge. In addition, we investigate the conditions under which a mental state model exists, characterizing a class of “goal-seeking” agents that can be modeled in this manner; and we suggest two criteria for choosing between consistent models, showing conditions under which they lead to a unique choice of model.

AAAI Conference 1997 Conference Paper

On the Axiomatization of Qualitative Decision Criteria

• Ronen I. Brafman

AAAI Conference 1996 Conference Paper

On the Foundations of Qualitative Decision Theory

• Ronen I. Brafman

This paper investigates the foundation of rnaxipnin, one of the central qualitative decision criteria, using the approach taken by Savage (Savage 1972) to investigate the foundation and rationality of classical decision theory. This approach asks “which behaviors could result from the use of a particular decision procedure? ” The answer to this question provides two important insights: (1) under what conditions can we employ a particular agent model, and (2) how rational is a particular decision procedure. Our main result is a constructive representation theorem in the spirit of Savage’ s result for expected utility maximization, which uses two choice axioms to characterize the maxapnin criterion. These axioms characterize agent behaviors that can be modeled compactly using the maxcirninmodel, and, with some reservations, indicate that rnaxionin is a reasonable decision criterion.

TARK Conference 1994 Conference Paper

Knowledge as a Tool in Motion Planning and Uncertainty

• Ronen I. Brafman
• Jean-Claude Latombe
• Yoram Moses
• Yoav Shoham

Inspired by the success of the distributed computing community in applying logics of knowledge and time to reasoning ahout distributed protocols, we aim for a similarly powerful and high-level abstraction when reasoning about control problems involving uncertainty. Here we concentrate on robot motion planning, with uncertainty in both control and sensing. This problem has already been well studied within the robotics community. Our contributions include the following: • We define, a new, naturM problem in this domain: obtaining a sound and complete termination condition, given initial and goal locations. • We define a high-level language, a logic of time and knowledge, to reason about motion plans in the presence of uncertainty, and use it to provide general conditions for the existence of sound and complete termination conditions for a broad class of motion plans. ®We characterize the optimal sound termination conditions for the general problem, relate them to a class of fundamental knowledge based protocols and provide a natural example of knowledge based protocols lacking a canonical implementation. 1 *Currently on sabbatical at the Oxford University Computing Laboratory, Oxford OX1 3QD England: The first part of this paper generalizes results of a previous paper by Brafman, I, atombe and Shoham ([BLS93]). Sections 4. 3 and 5 contain ne'w ~aterial.

AAAI Conference 1993 Conference Paper

Towards Knowledge-Level Analysis of Motion Planning

• Ronen I. Brafman

Inspired by the success of the distributed computing community in applying logics of knowledge and time to reasoning about distributed protocols, we aim for a similarly powerful and high-level abstraction when reasoning about control problems involving uncertainty. Here we concentrate on robot motion planning, with uncertainty in both control and sensing. This problem has already been well studied within the robotics community. Our contributions include the following: e We define a new, natural problem in this domain: obtaining a sound and complete termination condition, given initial and goal locations. o We consider a specific class of (simple) motion plans in Rn from the literature, and provide necessary and sufficient conditions for the existence of sound and complete termination conditions for plans in that class. l We define a high-level language, a logic of time and knowledge, to reason about motion plans in the presence of uncertainty, and use them to provide general conditions for the existence of sound and complete termination conditions for a broader class of motion plans.