Author name cluster

Nitin Yadav

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers

2 author rows

ECAI Conference 2023 Conference Paper

A Declarative Approach to Compact Controllers for FOND Planning via Answer Set Programming

Nitin Yadav
Sebastian Sardiña

We present an approach to non-deterministic planning under full observability via Answer Set Programming. The technique can synthesise compact policies, handle both fair and unfair actions simultaneously, and readily accommodate control knowledge and procedural domain constraints. We show that whereas compact controllers may yield sub-optimal behavior under a naive executor, optimality can be recovered under a smarter executor. The developed planner is succinct, elegant, and directly implementable, thus providing higher confidence of its correctness and ease of elaboration. Experimental results show that its performance is competitive.

Details

ECAI Conference 2020 Conference Paper

Is Hardness Inherent in Computational Problems? Performance of Human and Electronic Computers on Random Instances of the 0-1 Knapsack Problem

Nitin Yadav
Carsten Murawski
Sebastian Sardiña
Peter Bossaerts

Many cognitive problems people face have been shown to be computationally intractable. However, tractability is typically defined in terms of asymptotic worst-case behaviour of instances. One approach for studying typical cases of NP-complete problems is based on random instances. It has been shown that random instances of many NP-complete problems exhibit a phase transition in solvability and that hard instances tend to occur in this phase transition. Here, we characterise a phase transition in solvability for random instances of the 0-1 knapsack problem in terms of two simple instance properties. Subsequently, we show that compute time of algorithms peaks in the phase transition. Remarkably, the phase transition likewise predicts where people spend the most effort. Nevertheless, their performance decreases. This suggests that instances that are difficult for electronic computers are recognized as such by people, but the increased effort does not compensate for hardness. Given the ubiquity of the knapsack problem in every-day life, a better characterisation of the properties that make instances hard will help understand commonalities and differences in computation between human and digital computers, and to improve both decision environments (contracts, regulation) as well as human-computer interfaces.

Details

RLDM Conference 2019 Conference Abstract

Distributional Temporal Difference Learning for Finance: Dealing with Lep- tokurtic Rewards

Shijie Huang
Peter Bossaerts
Nitin Yadav

In traditional Reinforcement Learning (RL), agents aim at optimizing state-action choices based on recursive estimation of expected values. Here, we show that this approach fails when the period rewards (returns) are generated by a leptokurtic law, as is common in financial applications. Under leptokurtosis, outliers are frequent and large, causing the estimates of expected values, and hence, optimal policies, to change erratically. Distributional RL improves on this because it takes the entire distribution of outcomes into account, and hence, allows more efficient estimation of expected values. Here, we take this idea further and use the asymptotically most efficient estimator of expected values, namely, the Maximum Likelihood Estimator (MLE). In addition, since in our financial context the period reward distribution and the (asymp- totic) distribution of action-values (Q-values) are fundamentally different, with leptokurtosis affecting the former but not the latter, we estimate their means separately. We show how the resulting distributional RL (d-RL-MLE) learns much faster, and is robust once it settles on the optimal policy. Altogether, our results demonstrate that introducing domain-specific prior knowledge in a disciplined way improves performance and robustness of distributional RL.

PDF Details

AAMAS Conference 2018 Conference Paper

A new Hierarchical Agent Protocol Notation

Michael Winikoff
Nitin Yadav
Lin Padgham

Agent interaction protocols are a key aspect of the design of multiagent systems. However, commonly-used notations are, we argue, difficult to use, and lack expressiveness in certain areas. In this paper we present a new notation for expressing interaction protocols, focussing on key issues that we have found to be problematic. The notation is evaluated against criteria, and using a human subject evaluation of usability.

PDF

JAAMAS Journal 2017 Journal Article

A new Hierarchical Agent Protocol Notation

Michael Winikoff
Nitin Yadav
Lin Padgham

Abstract Agent interaction descriptions (or protocols) are a key aspect of the design of multi-agent systems. However, in the authors’ extensive experience, the notations commonly used for specification are both difficult to use, and lack expressiveness in certain areas. Some desired modular representations are impossible to express, while others result in specifications that are unwieldy and difficult to follow. In this paper we present a new notation for expressing interaction protocols, focussing on key issues that we have found to be problematic: the ability to define flexible data-driven protocols; representation of roles including their mapping to agents; and hierarchical modularity. We provide the semantics for our notation and illustrate its use with three diverse case studies. Finally we evaluate this notation using objectively assessable criteria that we argue contribute substantially to pragmatic usability, and using a human subject evaluation of the notation’s usability.

Details DOI

IJCAI Conference 2017 Conference Paper

Agent Design Consistency Checking via Planning

Nitin Yadav
John Thangarajah
Sebastian Sardina

In this work we present a novel approach to check the consistency of agent designs (prior to any implementation) with respect to the requirements specifications via automated planning. This checking is essentially a search problem which makes planning technology an appropriate solution. We focus our work on BDI agent systems and the Prometheus design methodology in order to directly compare our approach to previous work. Our experiments in more than 16K random instances prove that the approach is more effective than previous ones proposed: it achieves higher coverage, lower run-time, and importantly, can handle loops in the agent detailed design and unbounded subgoal reasoning.

PDF Details

ECAI Conference 2016 Conference Paper

Checking the Conformance of Requirements in Agent Designs Using ATL

Nitin Yadav
John Thangarajah

Intelligent agent systems built using the BDI model of agency have grown in popularity for implementing complex systems such as UAVs, military simulations, trading agents and intelligent games. The robust and flexible behaviours that these systems afford also makes testing the 'correctness' of these systems a non-trivial task. Whilst the main focus on existing work has been on checking the correctness of agent-programs, in this work we present an approach to formally verify agent-based designs for a particular BDI agent design methodology. The focus is on verifying whether the detailed design of the agents conform to the requirements specification. We present a sound and complete approach, formally verifiable properties, and an evaluation with respect to time and effectiveness.

Details

ICAPS Conference 2013 Conference Paper

Behavior Composition as Fully Observable Non-Deterministic Planning

Miquel Ramírez
Nitin Yadav
Sebastian Sardiña

The behavior composition problem involves the automatic synthesis of a controller able to “realize” (i. e. , implement) a target behavior module by suitably coordinating a collection of partially controllable available behaviors. In this paper, we show that the existence of a composition solution amounts to finding a strong cyclic plan for a special non-deterministic planning problem, thus establishing the formal link between the two synthesis tasks. Importantly, our results support the use of non-deterministic planing systemsfor solving composition problems in an off-the-shelf manner. We then empirically evaluate three state-of-the-art synthesis systems (a domain-independent automated planner and two game solvers based on model checking techniques) on various non-trivial composition instances. Our experiments show that while behavior composition is EXPTIME-complete, the current technology is already able to handle instances of significant complexity. Our work is, as far as we know, the first serious experimental work on behavior composition.

Details

IJCAI Conference 2013 Conference Paper

Behavior Composition Optimization

Nitin Yadav

The behavior composition problem involves the automatic synthesis of a controller that is able to “realize” (i. e. , implement) a desired target behavior specification by suitably coordinating a set of already available behaviors. While the problem has been thoroughly studied, one open issue has resisted a principled solution: if the target specification is not fully realizable, is there a way to realize it “at best”? In this doctoral work, we look at quantitative and qualitative ways to address this question.

PDF Details DOI

IJCAI Conference 2013 Conference Paper

Supremal Realizability of Behaviors with Uncontrollable Exogenous Events

Nitin Yadav
Paolo Felli
Giuseppe De Giacomo
Sebastian Sardina

The behavior composition problem involves the automatic synthesis of a controller able to “realize” (i. e. , implement) a desired target behavior specification by suitably coordinating a set of already available behaviors. While the problem has been thoroughly studied, one open issue has resisted a principled solution: if the target specification is not fully realizable, is there a way to realize it “at best”? In this paper we answer positively, by showing that there exists a unique supremal realizable target behavior satisfying the specification. More importantly we give an effective procedure to compute such a target. Then, we introduce exogenous events, and show that the supremal can again be computed, though this time, into two variants, depending on the ability to observe such events.

PDF Details DOI

IJCAI Conference 2013 Conference Paper

Using Strategic Logics to Reason about Agent Programs

Nitin Yadav
Sebastian Sardina

We propose a variant of Alternating-time Temporal Logic (ATL) grounded in the agents’ operational know-how, as defined by their libraries of abstract plans. In our logic, it is possible to refer to “rational” strategies for agents developed under the Belief-Desire-Intention agent paradigm. This allows us to express and verify properties of BDI systems using ATL-type logical frameworks.

PDF Details DOI

JELIA Conference 2012 Conference Paper

Qualitative Approximate Behavior Composition

Nitin Yadav
Sebastian Sardiña

Abstract The behavior composition problem involves automatically building a controller that is able to realize a desired, but unavailable, target system (e. g. , a house surveillance) by suitably coordinating a set of available components (e. g. , video cameras, blinds, lamps, a vacuum cleaner, phones, etc.) Previous work has almost exclusively aimed at bringing about the desired component in its totality, which is highly unsatisfactory for unsolvable problems. In this work, we develop an approach for approximate behavior composition without departing from the classical setting, thus making the problem applicable to a much wider range of cases. Based on the notion of simulation, we characterize what a maximal controller and the “closest” implementable target module (optimal approximation) are, and show how these can be computed using ATL model checking technology for a special case. We show the uniqueness of optimal approximations, and prove their soundness and completeness with respect to their imported controllers.

Details

JELIA Conference 2012 Conference Paper

Reasoning about Agent Programs Using ATL-Like Logics

Nitin Yadav
Sebastian Sardiña

Abstract We propose a variant of Alternating-time Temporal Logic (ATL) grounded in the agents’ operational know-how, as defined by their libraries of abstract plans. Inspired by ATLES, a variant itself of ATL, it is possible in our logic to explicitly refer to “rational” strategies for agents developed under the Belief-Desire-Intention agent programming paradigm. This allows us to express and verify properties of BDI systems using ATL-type logical frameworks.

Details

AAMAS Conference 2011 Conference Paper

Decision Theoretic Behavior Composition

Nitin Yadav
Sebastian Sardina

The behavior composition problem involves realizing a virtual target behavior (i. e. , the desired module) by suitably coordinating the execution of a set of partially controllable available components (e. g. , agents, devices, processes, etc. ) running in a shared partially predictable environment. All existing approaches to such problem have been framed within strict uncertainty settings. In this work, we propose a framework for automatic behavior composition which allows the seamless integration of classical behavior composition with decision-theoretic reasoning. Specifically, we consider the problem of maximizing the "expected realizability" of the target behavior in settings where the uncertainty can be quantified. Unlike previous proposals, the approach developed here is able to (better) deal with instances that do not accept "exact" solutions, thus yielding a more practical account for real domains. Moreover, it is provably strictly more general than the classical composition framework. Besides formally defining the problem and what counts as a solution, we show how a decision-theoretic composition problem can be solved by reducing it to the problem of finding an optimal policy in a Markov decision process.

PDF