Author name cluster

Yanjing Wang

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.

9 papers

1 author row

AIJ Journal 2024 Journal Article

Knowing how to plan about planning: Higher-order and meta-level epistemic planning

Yanjun Li
Yanjing Wang

Automated planning in AI and the logics of knowing how have close connections. In the recent literature, various planning-based know-how logics have been proposed and studied, making use of several notions of planning in AI. In this paper, we explore the reverse direction by using a multi-agent logic of knowing how to do know-how-based planning via model checking and theorem proving/satisfiability checking. Based on our logical framework, we propose two new classes of related planning problems: higher-order epistemic planning and meta-level epistemic planning, which generalize the current genre of epistemic planning in the literature. The former is for planning about planning, i. e. , planning with higher-order goals that are again about epistemic planning, e. g. , finding a plan for an agent to make sure p such that the adversary does not know how to make p false in the future. The latter is about planning at the meta-level by abstract reasoning combining knowledge-how from different agents, e. g. , given that i knows how to prove a lemma and i knows j knows how to prove the theorem once the lemma is proved, we should derive that i knows how to let j knows how to prove the theorem. To make these possible, our framework features not only the operators of know-that and know-how but also a temporal operator □, which can help in capturing both the local and global knowledge-how. We axiomatize this powerful logic over finite models with perfect recall and show its decidability. We also give a PTIME algorithm for the model checking problem over finite models.

Details DOI

I&C Journal 2023 Journal Article

Are bundles good deals for first-order modal logic?

Mo Liu
Anantha Padmanabha
R. Ramanujam
Yanjing Wang

Bundled products are often offered as good deals to customers. In first-order modal logic (FOML), when we bundle quantifiers and modalities together (as in ∃ x □, ◇ ∀ x, etc.), we get new logical operators whose combinations produce interesting fragments of FOML without any restriction on the arity of predicates, the number of variables, or the modal scope. It is well-known that finding decidable fragments of FOML is hard, so we may ask: do bundled fragments that exploit the distinct expressivity of FOML constitute good deals in balancing the expressivity and complexity? There are a few positive earlier results towards identifying the decidable ones. In this paper, we map the terrain of bundled fragments of FOML in (un)decidability, and in the cases without a definite answer yet, we show that they lack the finite model property. Moreover, whether the class of models considered has constant domains (across states/worlds) or increasing domains presents another layer of complexity. We also present the loosely bundled fragment, which generalizes the bundles and yet retains decidability (over increasing domain models).

Details DOI

AIJ Journal 2021 Journal Article

Planning-based knowing how: A unified approach

Yanjun Li
Yanjing Wang

Various logical notions of know-how have been recently proposed and studied in the literature based on different types of epistemic planning in different frameworks. This paper proposes a unified logical framework to incorporate the existing and some new notions of know-how. We define the semantics of the know-how operator using a unified notion of epistemic planning with parameters of different types of plans specified by a programming language. Surprisingly, via a highly unified completeness proof, we show that all the ten intuitive notions of plans discussed in this paper lead to exactly the same know-how logic, which is proven to be decidable. We also show that over finite models, the know-how logic based on knowledge-based plans requires an extension with an axiom capturing the compositionality of the plans. In the context of epistemic planning, our axiomatization results reveal the core principles behind the very idea of epistemic planning, independent of the particular notion of plans. Moreover, since epistemic planning can be expressed by the know-how modality in our object language, we can greatly generalize the planning problems that can be solved formally by model checking various formulas in our language.

Details DOI

AIJ Journal 2019 Journal Article

A dynamic epistemic framework for reasoning about conformant probabilistic plans

Yanjun Li
Barteld Kooi
Yanjing Wang

In this paper, we introduce a probabilistic dynamic epistemic logical framework that can be applied for reasoning and verifying conformant probabilistic plans in a single agent setting. In conformant probabilistic planning (CPP), we are looking for a linear plan such that the probability of achieving the goal after executing the plan is no less than a given threshold probability δ. Our logical framework can trace the change of the belief state of the agent during the execution of the plan and verify the conformant plans. Moreover, with this logic, we can enrich the CPP framework by formulating the goal as a formula in our language with action modalities and probabilistic beliefs. As for the main technical results, we provide a complete axiomatization of the logic and show the decidability of its validity problem.

Details DOI

IJCAI Conference 2017 Conference Paper

Strategically knowing how

Raul Fervari
Andreas Herzig
Yanjun Li
Yanjing Wang

In this paper, we propose a single-agent logic of goal-directed knowing how extending the standard epistemic logic of knowing that with a new knowing how operator. The semantics of the new operator is based on the idea that knowing how to achieve phi means that there exists a (uniform) strategy such that the agent knows that it can make sure phi. We give an intuitive axiomatisation of our logic and prove the soundness, completeness, and decidability of the logic. The crucial axioms relating knowing that and knowing how illustrate our understanding of knowing how in this setting. This logic can be used in representing and reasoning about knowledge-how.

PDF Details

AIJ Journal 2014 Journal Article

Hidden protocols: Modifying our expectations in an evolving world

Hans van Ditmarsch
Sujata Ghosh
Rineke Verbrugge
Yanjing Wang

When agents know a protocol, this leads them to have expectations about future observations. Agents can update their knowledge by matching their actual observations with the expected ones. They eliminate states where they do not match. In this paper, we study how agents perceive protocols that are not commonly known, and propose a semantics-driven logical framework to reason about knowledge in such scenarios. In particular, we introduce the notion of epistemic expectation models and a propositional dynamic logic-style epistemic logic for reasoning about knowledge via matching agentsʼ expectations to their observations. It is shown how epistemic expectation models can be obtained from epistemic protocols. Furthermore, a characterization is presented of the effective equivalence of epistemic protocols. We introduce a new logic that incorporates updates of protocols and that can model reasoning about knowledge and observations. Finally, the framework is extended to incorporate fact-changing actions, and a worked-out example is given.

Details DOI

IJCAI Conference 2013 Conference Paper

An Alternative Axiomatization of DEL and Its Applications

Yanjing Wang
Guillaume Aucher

In this paper, we provide a new axiomatization of the event-model-based Dynamic Epistemic Logic, based on the completeness proof method proposed in [Wang and Cao, 2013]. This axiomatization does not use any of the standard reduction axioms, but naturally captures the essence of the update product. We demonstrate the use of our new axiomatization and the corresponding proof techniques by three sets of results: characterization theorems of the update operations, representation theorems of the DEL-generatable epistemic temporal structures given a fixed event model, and a complete axiomatization of DEL on models with protocols.

PDF Details DOI

IJCAI Conference 2013 Conference Paper

Knowing That, Knowing What, and Public Communication: Public Announcement Logic with Kv Operators

Yanjing Wang
Jie Fan

In his seminal work [Plaza, 1989], Plaza proposed the public announcement logic (PAL), which is considered as the pilot logic in the field of dynamic epistemic logic. In the same paper, Plaza also introduced an interesting “know-value” operator Kv and listed a few valid formulas of PAL+Kv. However, it is unknown that whether these formulas, on top of the axioms for PAL, completely axiomatize PAL+Kv. In this paper, we first give a negative answer to this open problem. Moreover, we generalize the Kv operator and show that in the setting of PAL, replacing the Kv operator with its generalized version does not increase the expressive power of the resulting logic. This suggests that we can simply use the more flexible generalization instead of the original PAL+Kv. As the main result, we give a complete proof system for PAL plus the generalized operator based on a complete axiomatization of epistemic logic with the same operator in the single-agent setting. Key words: public announcement logic, know-value operator, modal logic, multi-agent system

PDF Details DOI

AAMAS Conference 2010 Conference Paper

Logic of Information Flow on Communication Channels

Yanjing Wang
Floor Sietsma
Jan van Eijck

We develop an epistemic logic to specify and reason about information flow and its underlying communication channels. By combining ideas from Dynamic Epistemic Logic (DEL) and InterpretedSystems (IS), our semantics offers a natural and neat way of modelling multi-agent communication scenarios with different assumptions about the observational power of agents.

PDF