Ronen Brafman

PRL Workshop 2024 Workshop Paper

Online Planning in MDPs with Stochastic Durative Actions

• Tal Berman
• Ronen Brafman
• Erez Karpas

5 10 15 20 25 30 35 40 Markov Decision Processes (MDPs) are a popular model for probabilistic planning. Actions in MDPs are applied sequentially, and their effects are instantaneous. Yet, real-world scenarios often involve actions with duration and parallel action execution. This paper considers CoMDPs, a model that extends MDPs with durative, concurrent actions, and describes TP-MCTS, an online algorithm for solving CoMDPs that combines Monte Carlo Tree Search (MCTS) with techniques used in classical temporal planning. TP-MCTS uses a compilation of durative actions to Start and End actions and enhances each tree node with a Simple Temporal Network to maintain temporal consistency and schedule the plan’s action. Our empirical evaluation demonstrates the efficacy of the TPMCTS algorithm in tackling CoMDPs.

AAAI Conference 2020 Conference Paper

Reinforcement Learning with Non-Markovian Rewards

• Maor Gaon
• Ronen Brafman

The standard RL world model is that of a Markov Decision Process (MDP). A basic premise of MDPs is that the rewards depend on the last state and action only. Yet, many real-world rewards are non-Markovian. For example, a reward for bringing coffee only if requested earlier and not yet served, is non-Markovian if the state only records current requests and deliveries. Past work considered the problem of modeling and solving MDPs with non-Markovian rewards (NMR), but we know of no principled approaches for RL with NMR. Here, we address the problem of policy learning from experience with such rewards. We describe and evaluate empirically four combinations of the classical RL algorithm Q-learning and R-max with automata learning algorithms to obtain new RL algorithms for domains with NMR. We also prove that some of these variants converge to an optimal policy in the limit.

AAAI Conference 2018 Conference Paper

LTLf/LDLf Non-Markovian Rewards

• Ronen Brafman
• Giuseppe De Giacomo
• Fabio Patrizi

In Markov Decision Processes (MDPs), the reward obtained in a state is Markovian, i. e. , depends on the last state and action. This dependency makes it difficult to reward more interesting long-term behaviors, such as always closing a door after it has been opened, or providing coffee only following a request. Extending MDPs to handle non-Markovian reward functions was the subject of two previous lines of work. Both use LTL variants to specify the reward function and then compile the new model back into a Markovian model. Building on recent progress in temporal logics over finite traces, we adopt LDLf for specifying non-Markovian rewards and provide an elegant automata construction for building a Markovian model, which extends that of previous work and offers strong minimality and compositionality guarantees.

AAAI Conference 2014 Conference Paper

A Relevance-Based Compilation Method for Conformant Probabilistic Planning

• Ran Taig
• Ronen Brafman

Conformant probabilistic planning (CPP) differs from conformant planning (CP) by two key elements: the initial belief state is probabilistic, and the conformant plan must achieve the goal with probability ≥ θ, for some 0 < θ ≤ 1. In earlier work we observed that one can reduce CPP to CP by finding a set of initial states whose probability ≥ θ, for which a conformant plan exists. In previous solvers we used the underlying planner to select this set of states and to plan for them simultaneously. Here we suggest an alternative approach: start with relevance analysis to determine a promising set of initial states on which to focus. Then, call an off-the-shelf conformant planner to solve the resulting problem. This approach has a number of advantages. First, instead of depending on the heuristic function to select the set of initial states, we can introduce specific, efficient relevance reasoning techniques. Second, we can benefit from optimizations used by conformant planners that are unsound when applied to the original CPP. Finally, we are free to use any existing (or new) CP solver. Consequently, the new planner dominates previous solvers on almost all domains and scales to instances that were not solved before.

AAAI Conference 2013 Conference Paper

Cost-Optimal Planning by Self-Interested Agents

• Raz Nissim
• Ronen Brafman

As our world becomes better connected and autonomous agents no longer appear to be science fiction, a natural need arises for enabling groups of selfish agents to cooperate in generating plans for diverse tasks that none of them can perform alone in a cost-effective manner. While most work on planning for/by selfish agents revolves around finding stable solutions (e. g. , Nash Equilibrium), this work combines techniques from mechanism design with a recently introduced method for distributed planning, in order to find cost optimal (and, thus, social welfare maximizing) solutions. Based on the Vickrey-Clarke-Groves mechanisms, we present both a centralized, and a privacy-preserving distributed mechanism.

AAAI Conference 2013 Conference Paper

Qualitative Planning under Partial Observability in Multi-Agent Domains

• Ronen Brafman
• Guy Shani
• Shlomo Zilberstein

Decentralized POMDPs (Dec-POMDPs) provide a rich, attractive model for planning under uncertainty and partial observability in cooperative multi-agent domains with a growing body of research. In this paper we formulate a qualitative, propositional model for multi-agent planning under uncertainty with partial observability, which we call Qualitative Dec-POMDP (QDec-POMDP). We show that the worst-case complexity of planning in QDec-POMDPs is similar to that of Dec-POMDPs. Still, because the model is more “classical” in nature, it is more compact and easier to specify. Furthermore, it eases the adaptation of methods used in classical and contingent planning to solve problems that challenge current Dec-POMDPs solvers. In particular, in this paper we describe a method based on compilation to classical planning, which handles multi-agent planning problems significantly larger than those handled by current Dec-POMDP algorithms.

AAAI Conference 2012 Conference Paper

A Multi-Path Compilation Approach to Contingent Planning

• Ronen Brafman
• Guy Shani

We describe a new sound and complete method for compiling contingent planning problems with sensing actions into classical planning. Our method encodes conditional plans within a linear, classical plan. This allows our planner, MPSR, to reason about multiple future outcomes of sensing actions, and makes it less susceptible to dead-ends. MPRS, however, generates very large classical planning problems. To overcome this, we use an incomplete variant of the method, based on state sampling, within an online replanner. On most current domains, MPSR finds plans faster, although its plans are often longer. But on a new challenging variant of Wumpus with dead-ends, it finds smaller plans, faster, and scales better.

AAAI Conference 2012 Conference Paper

Lifted MEU by Weighted Model Counting

• Udi Apsel
• Ronen Brafman

Recent work in the field of probabilistic inference demonstrated the efficiency of weighted model counting (WMC) engines for exact inference in propositional and, very recently, first order models. To date, these methods have not been applied to decision making models, propositional or first order, such as influence diagrams, and Markov decision networks (MDN). In this paper we show how this technique can be applied to such models. First, we show how WMC can be used to solve (propositional) MDNs. Then, we show how this can be extended to handle a first-order model – the Markov Logic Decision Network (MLDN). WMC offers two central benefits: it is a very simple and very efficient technique. This is particularly true for the firstorder case, where the WMC approach is simpler conceptually, and, in many cases, more effective computationally than the existing methods for solving MLDNs via first-order variable elimination, or via propositionalization. We demonstrate the above empirically.

AAMAS Conference 2012 Conference Paper

Multi-Agent A* for Parallel and Distributed Systems

• Raz Nissim
• Ronen Brafman

Search is among the most fundamental techniques for problem solving, and A* is probably the best known heuristic search algorithm. In this paper we adapt A* to the multiagent setting, focusing on multi-agent planning problems. We provide a simple formulation of multi-agent A*, with a parallel and distributed variant. Our algorithms exploit the structure of multi-agent problems to not only distribute the work efficiently among different agents, but also to remove symmetries and reduce the overall workload. Given a multi-agent planning problem in which agents are not tightly coupled, our parallel version of A* leads to super-linear speedup, solving benchmark problems that have not been solved before. In its distributed version, the algorithm ensures that private information is not shared among agents, yet computation is still efficient – sometimes even more than centralized search – despite the fact that each agent has access to partial information only.

AAAI Conference 2011 Conference Paper

Planning for Operational Control Systems with Predictable Exogenous Events

• Ronen Brafman
• Carmel Domshlak
• Yagil Engel
• Zohar Feldman

Various operational control systems (OCS) are naturally modeled as Markov Decision Processes. OCS often enjoy access to predictions of future events that have substantial impact on their operations. For example, reliable forecasts of extreme weather conditions are widely available, and such events can affect typical request patterns for customer response management systems, the flight and service time of airplanes, or the supply and demand patterns for electricity. The space of exogenous events impacting OCS can be very large, prohibiting their modeling within the MDP; moreover, for many of these exogenous events there is no useful predictive, probabilistic model. Realtime predictions, however, possibly with a short lead-time, are often available. In this work we motivate a model which combines offline MDP in- finite horizon planning with realtime adjustments given specific predictions of future exogenous events, and suggest a framework in which such predictions are captured and trigger real-time planning problems. We propose a number of variants of existing MDP solution algorithms, adapted to this context, and evaluate them empirically.

AAAI Conference 2011 Conference Paper

The Next Best Solution

• Ronen Brafman
• Enrico Pilotto
• Francesca Rossi
• Domenico Salvagnin
• Kristen Venable
• Toby Walsh

We study the computational complexity of finding the next most preferred solution in some common formalisms for representing constraints and preferences. The problem is computationally intractable for CSPs, but is polynomial for tree-shaped CSPs and tree-shaped fuzzy CSPs. On the other hand, it is intractable for weighted CSPs, even under restrictions on the constraint graph. For CP-nets, the problem is polynomial when the CP-net is acyclic. This remains so if we add (soft) constraints that are tree-shaped and topologically compatible with the CP-net.

AAMAS Conference 2010 Conference Paper

A General, Fully Distributed Multi-Agent Planning Algorithm

• Raz Nissim
• Ronen Brafman
• Carmel Domshlak

We present a fully distributed multi-agent planning algorithm. Our methodology uses distributed constraint satisfaction tocoordinate between agents, and local planning to ensure theconsistency of these coordination points. To solve the distributedCSP efficiently, we must modify existing methods to takeadvantage of the structure of the underlying planning problem. Inmulti-agent planning domains with limited agent interaction, ouralgorithm empirically shows scalability beyond state of the artcentralized solvers. Our work also provides a novel, real-worldsetting for testing and evaluating distributed constraint satisfactionalgorithms in structured domains and illustrates how existingtechniques can be altered to address such structure.

AAAI Conference 2010 Conference Paper

Decomposed Utility Functions and Graphical Models for Reasoning about Preferences

• Ronen Brafman
• Yagil Engel

Recently, Brafman and Engel (2009) proposed new concepts of marginal and conditional utility that obey additive analogues of the chain rule and Bayes rule, which they employed to obtain a directed graphical model of utility functions that resembles Bayes nets. In this paper we carry this analogy a step farther by showing that the notion of utility independence, built on conditional utility, satisfies identical properties to those of probabilistic independence. This allows us to formalize the construction of graphical models for utility functions, directed and undirected, and place them on the firm foundations of Pearl and Paz’s axioms of semi-graphoids. With this strong equivalence in place, we show how algorithms used for probabilistic reasoning such as Belief Propagation (Pearl 1988) can be replicated to reasoning about utilities with the same formal guarantees, and open the way to the adaptation of additional algorithms.

KR Conference 2010 Conference Paper

Finding the next solution in constraint- and preference-based knowledge representation formalisms

• Ronen Brafman
• Francesca Rossi
• Domenico Salvagnin
• Kristen Brent Venable
• Toby Walsh

In constraint or preference reasoning, a typical task is to compute a solution, or an optimal solution. However, when one has already a solution, it may be important to produce the next solution following the given one in a linearization of the solution ordering where more preferred solutions are ordered first. In this paper, we study the computational complexity of finding the next solution in some common preference-based representation formalisms. We show that this problem is hard in general CSPs, but it can be easy in tree-shaped CSPs and tree-shaped fuzzy CSPs. However, it is difficult in weighted CSPs, even if we restrict the shape of the constraint graph. We also consider CP-nets, showing that the problem is easy in acyclic CP-nets, as well as in constrained acyclic CP-nets where the (soft) constraints are tree-shaped and topologically compatible with the CP-net.

AAAI Conference 2010 Conference Paper

Transferable Utility Planning Games

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

Connecting between standard AI planning constructs and a classical cooperative model of transferable-utility coalition games, we introduce the notion of transferable-utility (TU) planning games. The key representational property of these games is that coalitions are valued implicitly based on their ability to carry out efficient joint plans. On the side of the expressiveness, we show that existing succinct representations of monotonic TU games can be efficiently compiled into TU planning games. On the side of computation, TU planning games allow us to provide some of the strongest to date tractability results for core-existence and core-membership queries in succinct TU coalition games.

IJCAI Conference 2007 Conference Paper

• Nicolas Meuleau
• Ronen Brafman

Many MDPs exhibit an hierarchical structure where the agent needs to perform various subtasks that are coupled only by a small sub-set of variables containing, notably, shared resources. Previous work has shown how this hierarchical structure can be exploited by solving several sub-MDPs representing the different subtasks in different calling contexts, and a root MDP responsible for sequencing and synchronizing the subtasks, instead of a huge MDP representing the whole problem. Another important idea used by efficient algorithms for solving flat MDPs, such as (L)AO* and (L)RTDP, is to exploit reachability information and an admissible heuristics in order to accelerate the search by pruning states that cannot be reached from a given starting state under an optimal policy. In this paper, we combine both ideas and develop a variant of the AO* algorithm for performing forward heuristic search in hierarchical models. This algorithm shows great performance improvements over hierarchical approaches using standard MDP solvers such as Value Iteration, as well as with respect to AO* applied to a flat representation of the problem. Moreover, it presents a general new method for accelerating AO* and other forward search algorithms. Substantial performance gains may be obtained in these algorithms by partitioning the set of search nodes, and solving a subset of nodes completely before propagating the results to other subsets.

AAAI Conference 2005 Conference Paper

Optimal Efficient Learning Equilibrium: Imperfect Monitoring in Symmetric Games

• Ronen Brafman

Efficient Learning Equilibrium (ELE) is a natural solution concept for multi-agent encounters with incomplete information. It requires the learning algorithms themselves to be in equilibrium for any game selected from a set of (initially unknown) games. In an optimal ELE, the learning algorithms would efficiently obtain the surplus the agents would obtain in an optimal Nash equilibrium of the initially unknown game which is played. The crucial part is that in an ELE deviations from the learning algorithms would become non-beneficial after polynomial time, although the game played is initially unknown. While appealing conceptually, the main challenge for establishing learning algorithms based on this concept is to isolate general classes of games where an ELE exists. Unfortunately, it has been shown that while an ELE exists for the setting in which each agent can observe all other agents’ actions and payoffs, an ELE does not exist in general when the other agents’ payoffs cannot be observed. In this paper we provide the first positive results on this problem, constructively proving the existence of an optimal ELE for the class of symmetric games where an agent can not observe other agents’ payoffs.

IJCAI Conference 2005 Conference Paper

Planning with Continuous Resources in Stochastic Domains

• Mausam
• Emmanuel Benazera
• Ronen Brafman
• Nicolas Meuleau
• Eric A

We consider the problem of optimal planning in stochastic domains with resource constraints, where resources are continuous and the choice of action at each step may depend on the current resource level. Our principal contribution is the HAO* algorithm, a generalization of the AO* algorithm that performs search in a hybrid state space that is modeled using both discrete and continuous state variables. The search algorithm leverages knowledge of the starting state to focus computational effort on the relevant parts of the state space. We claim that this approach is especially effective when resource limitations contribute to reachability constraints. Experimental results show its effectiveness in the domain that motivates our research – automated planning for planetary exploration rovers.

NeurIPS Conference 2004 Conference Paper

Resolving Perceptual Aliasing In The Presence Of Noisy Sensors

• Guy Shani
• Ronen Brafman

Agents learning to act in a partially observable domain may need to overcome the problem of perceptual aliasing i. e. , different states that appear similar but require different responses. This problem is exacer- bated when the agent's sensors are noisy, i. e. , sensors may produce dif- ferent observations in the same state. We show that many well-known reinforcement learning methods designed to deal with perceptual alias- ing, such as Utile Suffix Memory, finite size history windows, eligibility traces, and memory bits, do not handle noisy sensors well. We suggest a new algorithm, Noisy Utile Suffix Memory (NUSM), based on USM, that uses a weighted classification of observed trajectories. We compare NUSM to the above methods and show it to be more robust to noise.

NeurIPS Conference 2002 Conference Paper

Efficient Learning Equilibrium

• Ronen Brafman
• Moshe Tennenholtz

We introduce efficient learning equilibrium (ELE), a normative ap(cid: 173) proach to learning in non cooperative settings. In ELE, the learn(cid: 173) ing algorithms themselves are required to be in equilibrium. In addition, the learning algorithms arrive at a desired value after polynomial time, and deviations from a prescribed ELE become ir(cid: 173) rational after polynomial time. We prove the existence of an ELE in the perfect monitoring setting, where the desired value is the expected payoff in a Nash equilibrium. We also show that an ELE does not always exist in the imperfect monitoring case. Yet, it exists in the special case of common-interest games. Finally, we extend our results to general stochastic games.