Ing. Rostislav Horčík, Ph.D.

Effective decision making while competing for limited resources in adversarial environments is important for many real-world applications (e.g. two Taxi companies competing for customers). Decision-making techniques such as Automated planning have to take into account possible actions of adversary (or competing) agents. That said, the agent should know what the competitor will likely do and then generate its plan accordingly. In this paper we propose a novel approach for estimating strategies of the adversary (or the competitor), sampling its actions that might hinder agent's goals by interfering with the agent's actions. The estimated competitor strategies are used in plan generation such that agent's actions have to be applied prior to the ones of the competitor, whose estimated times dictate the deadlines. We empirically evaluate our approach leveraging sampling of competitor's actions by comparing it to the naive approach optimizing the make-span (not taking the competing agent into account at all) and to Nash Equilibrium (mixed) strategies.

It is known that every countable totally ordered set can be embedded into a countable dense one. We extend this result to totally ordered commutative monoids and to totally ordered commutative residuated lattices (the latter result fails in the absence of commutativity). The latter has applications to density elimination of semilinear substructural logics. In particular we obtain as a corollary a purely algebraic proof of the standard completeness of uninorm logic; the advantage over the known proof-theoretic proof and the semantical proof is that it is extremely short and transparent and all details can be verified easily using standard algebraic constructions.

Effective planning while competing for limited resources is crucial in many real-world applications such as on-demand transport companies competing for passengers. Planning techniques therefore have to take into account possible actions of an adversarial agent. Such a challenge that can be tackled by leveraging game-theoretical methods such as Double Oracle. This paper aims at the scalability issues arising from combining planning techniques with Double Oracle. In particular, we propose an abstraction-based heuristic for deciding how resources will be collected (e.g. which car goes for which passenger and in which order) and we propose a method for decomposing planning tasks into smaller ones (e.g. generate plans for each car separately). Our empirical evaluation shows that our proposed approach considerably improves scalability compared to the state-of-the-art techniques.

Classical planning tasks are modelled in PDDL which is a schematic language based on first-order logic. Most of the current planners turn this lifted representation into a propositional one via a grounding process. However, grounding may cause an exponential blowup. Therefore it is important to investigate methods for searching for plans on the lifted level. To build a lifted state-based planner, it is necessary to invent lifted heuristics. We introduce maps between PDDL tasks preserving plans allowing to transform a PDDL task into a smaller one. We propose a novel method for computing lifted (admissible) delete-free relaxed heuristics via grounding of the smaller task and computing the (admissible) delete-free relaxed heuristics there. This allows us to transfer the knowledge about relaxed heuristics from the grounded level to the lifted level.

This paper shows that domain-independent tools from classical planning can be used to model and solve a broad class of game-theoretic problems we call Cost-Adversarial Planning Games (CAPGs). We define CAPGs as 2-player normal-form games specified by a planning task and a finite collection of cost functions. The first player (a planning agent) strives to solve a planning task optimally but has limited knowledge about its action costs. The second player (an adversary agent) controls the actual action costs. Even though CAPGs need not be zero-sum, every CAPG has an associated zero-sum game whose Nash equilibrium provides the optimal randomized strategy for the planning agent in the original CAPG. We show how to find the Nash equilibrium of the associated zero-sum game using a cost-optimal planner via the Double Oracle algorithm. To demonstrate the expressivity of CAPGs, we formalize a patrolling security game and several IPC domains as CAPGs.

Effective plan generation in adversarial environments has totake into account possible actions of adversary agents, i.e.,the agent should know what the competitor will likely do.In this paper we propose a novel approach for estimatingstrategies of the adversary, sampling actions that interferewith the agent’s ones. The estimated competitor strategies areused in plan generation by considering that agent’s actionshave to be applied prior to the ones of the competitor, whoseestimated times dictate the agent’s deadlines. Missing thesedeadlines entails additional plan cost

Many efficient algorithms have been designed to recover Nash equilibria of various classes of finite games. Special classes of continuous games with infinite strategy spaces, such as polynomial games, can be solved by semidefinite programming. In general, however, continuous games are not directly amenable to computational procedures. In this contribution, we develop an iterative strategy generation technique for finding a Nash equilibrium in a whole class of continuous two-person zero-sum games with compact strategy sets. The procedure, which is called the double oracle algorithm, has been successfully applied to large finite games in the past. We prove the convergence of the double oracle algorithm to a Nash equilibrium. Moreover, the algorithm is guaranteed to recover an approximate equilibrium in finitely-many steps. Our numerical experiments show that it outperforms fictitious play on several examples of games appearing in the literature. In particular, we provide a detailed analysis of experiments with a version of the continuous Colonel Blotto game.

Detection of redundant operators that can be safely removed from the planning task is an essential technique allowing to greatly improve performance of planners. In this paper, we employ structure-preserving maps on labelled transition systems (LTSs), namely endomorphisms well known from model theory, in order to detect redundancy. Computing endomorphisms of an LTS induced by a planning task is typically infeasible, so we show how to compute some of them on concise representations of planning tasks such as finite domain representations and factored LTSs. We formulate the computation of endomorphisms as a constraint satisfaction problem (CSP) that can be solved by an off-the-shelf CSP solver. Finally, we experimentally verify that the proposed method can find a sizeable number of redundant operators on the standard benchmark set.

Classical planning tasks are usually modeled in the PDDL which is a schematic language based on first-order logic. Nevertheless, most of the current planners turn this first-order representation into a propositional one via the grounding process. It is well known that the grounding process may cause an exponential blowup. Therefore it is important to detect which grounded atoms are redundant in a sense that they are not necessary for finding a plan and therefore the grounding process does not need to generate them. This is usually done by a relaxed reachability analysis, which can be improved by employing structural symmetries. Symmetries are bijective self-maps preserving the structure of the PDDL task. In this paper, we introduce a new method which is based on self-maps preserving the structure but which need not be bijective. We call these maps PDDL endomorphisms and we show that they can be used for pruning of redundant objects even if they appear in a reachable atom. We formulate the computation of endomorphisms as a constraint satisfaction problem (CSP) that can be solved by an off-the-shelf CSP solver.

In real-world scenarios the environment is rarely static. Ex-ogenous events might occur without the consent of the agentacting in such a dynamic environment. Events account foracts of nature without specific intentions, or actions of otheragents having their own intentions.Restricting on two actors, an agent applying actions and anenvironment applying events, we, in this paper, elaborate onfive different models of how these actors can interact. Foreach actor, we assume full observability and full knowledgeof actions and events. In particular, we focus on action-eventconflicts that arise from the fact that one actor cannot con-trol the other actor while concerning a classical and temporalsettings.

Effective and efficient reasoning in adversarial environments is important for many real-world applications ranging from cybersecurity to military operations. Deliberative reasoning techniques, such as Automated Planning, often restrict to static environments where only an agent can make changes by its actions. On the other hand, such techniques are effective and can generate non-trivial solutions. To explicitly reason in environments with an active adversary such as zero-sum games, the game-theoretic framework such as the Double Oracle algorithm can be leveraged. In this paper, we leverage the notions of critical and adversary actions, where critical actions should be applied before the adversary ones. We propose heuristics that provide a guidance for planners about what (critical) actions and in which order have to be applied in a good plan. We empirically evaluate our approach in terms of quality of generated strategies (by leveraging Double Oracle) and CPU time required to generated such strategies.

Potential heuristics assign a numerical value (potential) to each fact and compute the heuristic value for a given state as the sum of these potentials. A mutex is an invariant stating that a certain combination of facts cannot be part of any reachable state. In this paper, we use mutexes to improve potential heuristics in two ways. First, we show that the mutex-based disambiguations of the goal and preconditions of operators leads to a less constrained linear program yielding stronger heuristics. Second, we utilize mutexes in a construction of new optimization functions based on counting of the number of states containing certain sets of facts. The experimental evaluation shows a significant increase in the number of solved tasks.

In a nutshell, zero-sum games represent scenarios where twoagents compete for the same goals such that each goal canbe achieved by at most one of the agents. The goals are, forexample, collecting limited resources or transporting passen-gers from their given location of origin to a required destina-tion. To achieve the goals, the agent might generate a plan.Plan generation, however, has to take possible actions of theadversary into consideration.In this paper, considering planning in zero-sum games, wepropose a heuristic approach for estimating strategies of theadversary, more specifically distribution of possible applica-tion times of its actions interfering with some of the agent’sactions. The agent’s actions in question have to be appliedbefore those of the adversary, whose estimated times hencerepresent their deadlines. Missing the deadlines can be repre-sented by action cost, so generated plans can be optimised forminimum total action cost. We empirically evaluate our ap-proach by comparing it to the baseline approach (plan gener-ation without taking adversary into account) and to the state-of-the-art approach leveraging the Double Oracle algorithmfor computing adversary strategies.

Among the class of finite integral commutative residuated chains (ICRCs), we identify those algebras which can be obtained as a nuclear retraction of a conuclear contraction of a totally ordered Abelian l-group. We call the ICRCs satisfying this condition regular. Then we discuss the structure of finite regular ICRCs. Finally, we prove that the class of regular members generate a strictly smaller variety than the variety generated by ICRCs.

It is known that there are only two cancellative atoms in the subvariety lattice of residuated lattices, namely the variety of Abelian l-groups CLG generated by the additive l-group of integers and the variety CLG(-) generated by the negative cone of this l-group. In this paper we consider all cancellative residuated chains arising on 2-generated submonoids of natural numbers and show that almost all of them generate a cover of CLG(-). This proves that there are infinitely many covers above CLG(-) which are commutative, integral, and representable.

In this article, solutions to three open problems on ordered commutative monoids posed in Evans et al. (2001, Semigroup forum, 62, 249-278) [4] are presented. By an ordered monoid, we always mean a totally ordered monoid. All the problems are related to the class of ordered commutative monoids which are homomorphic images of ordered free commutative monoids.

This paper investigates a quasi-variety of representable integral commutative residuated lattices axiomatized by the quasi-identity resulting from the well-known Wajsberg identity (p q) q (q p) p if it is written as a quasi-identity, i. e., (p q) q 1 (q p) p 1. We prove that this quasi-identity is strictly weaker than the corresponding identity. On the other hand, we show that the resulting quasi-variety is in fact a variety and provide an axiomatization. The obtained results shed some light on the structure of Archimedean integral commutative residuated chains. Further, they can be applied to various subvarieties of MTL-algebras, for instance we answer negatively Hájek's question asking whether the variety of MTL-algebras is generated by its Archimedean members

In this paper we present a different proof of the standard completeness theorem for the monoidal t-norm based logic. In fact, we prove even more since we show that MTL is complete w.r.t. the class of standard MTL-algebras with finite congruence lattice.

Formal systems of fuzzy logic (including the well-known Lukasiewicz and Godel-Dummett infinite-valued logics) are well-established logical systems and respected members of the broad family of the so-called substructural logics closely related to the famous logic BCK. The Study of fragments of logical systems is an important issue of research in any class of non-classical logics. Here we study the fragments of nine prominent fuzzy logics to all sublanguages containing implication. However, the results achieved in the paper for those nine logics are usually corollaries of theorems with much wider scope of applicability. In particular, we show how many of these fragments are really distinct and we find axiomatic systems for most of them. In fact, we construct strongly separable axiomatic systems for eight of our nine logics. We also fully answer the question for which of the studied fragments the corresponding class of algebras forms a variety.

The goal of this paper is to push Forward the development of the. apparatus of the Fuzzy Class theory. We concentrate oil three areas: strengthening the universal quantifier, formalizing the idea that 'similar' fuzzy sets fulfill their properties to 'similar' degrees, and embedding of classical crisp theories into Fuzzy Class theory.

It is well known that MTL satisfies the finite embeddability property. Thus MTL is complete w. r. t. the class of all finite MTL-chains. In order to reach a deeper understanding of the structure of this class, we consider the extensions of MTL by adding the generalized contraction since each finite MTL-chain satisfies a form of this generalized contraction. Simultaneously, we also consider extensions of MTL by the generalized excluded middle laws introduced in [9] and the axiom of weak cancellation defined in [31]. The algebraic counterpart of these logics is studied characterizing the subdirectly irreducible, the semisimple, and the simple algebras. Finally, some important algebraic and logical properties of the considered logics are discussed: local finiteness, finite embeddability property, finite model property, decidability, and standard completeness.

It is well-known that Hájek's Basic Fuzzy Logic (BL), Lukasiewicz logic, and product logic are not strongly standard complete. On the other hand Esteva and Godo's Monoidal T-norm Based Logic (MTL) and its involutive extension IMTL are strongly standard complete. In this paper we show that PiMTL (an extension of MTL by the axioms characteristic of product logic) does not enjoy the strong standard completeness theorem like BL, Lukasiewicz, and product logic.

IIMTL-algebras were introduced as an algebraic counterpart of the cancellative extension of monoidal t-norm based logic. It was shown that they form a variety generated by IIMTL-chains on the real interval [0, 1]. In this paper the structure of these generators is investigated. The results illuminate the structure of cancellative integral commutative residuated. chains, because every such algebra belongs to the quasivariety generated by the zero-free subreducts on (0, 1] of all IIMTL-chains on [0, 1].

It is known that the inonoidal t-norm based logic (MTL) and many of its schematic extensions' are decidable. The usual way how to prove decidability of some schematic extension of MTL is to show that the corresponding class of algebras of truth values has the finite model property (FIMP) or the finite embeddability property (FEP). However this method does not work for the extensions whose corresponding classes of algebras have only trivial finite members. Typical examples of such extensions are the product logic and the cancellative extension of MTL (Gamma IMTL) because the only finite algebras belonging to the corresponding varieties are finite Boolean algebras. The product, logic is known to be decidable because of its connection with ordered Abelian groups. However the decidability of Gamma IMTL was not known. This paper solves this problem.

In this paper we investigate the problem which varities of n-contractive MTL-algebras and IMTL-algebras are locally finite. We prove that the variety of n-contractive MTL-algebras and IMTL-algebras are not locally finite for n greater or equal 3. We also deal with the case of simple n-contractive MTL-algebras and IMTL-algebras.

The paper deals with the monoidal t-norm based logic satisfying a weaker form of the cancellation law. In particular, its logical and algebraic properties like (finite) strong standard completeness or finite embeddability property are studied.

PiMTL is a schematic extension of the monoidal t-norm based logic (MTL) by the characteristic axioms of product logic. In this paper we prove that PiMTL satisfies the standard completeness theorem. From the algebraic point of view, we show that the class of PiMTL-algebras (bounded commutative cancellative residuated l-monoids) in the real unit interval [0,1] generates the variety of all PiMTL-algebras.

Among all many-valued logics the Lu logic plays a fundamental role. However expressive power of this logic is restricted to piecewise linear functions. In this paper we enrich the language of Lu logic by adding a new connective which expresses multiplication. The resulting logic PL is defined and developed. We also deal with several extensions of this logic. At the end of the paper, the predicate version of PL logic is introduced and developed.

The validation set of a formula in a fuzzy logic is the set of all truth values which this formula may achieve. We summarize and extend recent results on characterizations of validation sets in various fuzzy logics.