| 1. |
- Aghighi, Meysam, et al.
(author)
-
Refining complexity analyses in planning by exploiting the exponential time hypothesis
- 2016
-
In: Annals of Mathematics and Artificial Intelligence. - : SPRINGER. - 1012-2443 .- 1573-7470. ; 78:2, s. 157-175
-
Journal article (peer-reviewed)abstract
- The use of computational complexity in planning, and in AI in general, has always been a disputed topic. A major problem with ordinary worst-case analyses is that they do not provide any quantitative information: they do not tell us much about the running time of concrete algorithms, nor do they tell us much about the running time of optimal algorithms. We address problems like this by presenting results based on the exponential time hypothesis (ETH), which is a widely accepted hypothesis concerning the time complexity of 3-SAT. By using this approach, we provide, for instance, almost matching upper and lower bounds onthe time complexity of propositional planning.
|
|
| 2. |
- Alberti, Marco, et al.
(author)
-
Observation Strategies for Event Detection with Incidence on Runtime Verification : Theory, Algorithms, Experimentation
- 2011
-
In: Annals of Mathematics and Artificial Intelligence. - : Springer. - 1012-2443 .- 1573-7470. ; 62:3-4, s. 161-186
-
Journal article (peer-reviewed)abstract
- Many applications (such as system and user monitoring, runtime verification, diagnosis, observation-based decision making, intention recognition) all require to detect the occurrence of an event in a system, which entails the ability to observe the system. Observation can be costly, so it makes sense to try and reduce the number of observations, without losing full certainty about the event’s actual occurrence. In this paper, we propose a formalization of this problem. We formally show that, whenever the event to be detected follows a discrete spatial or temporal pattern, then it is possible to reduce the number of observations. We discuss exact and approximate algorithms to solve the problem, and provide an experimental evaluation of them. We apply the resulting algorithms to verification of linear temporal logics formulæ. Finally, we discuss possible generalizations and extensions, and, in particular, how event detection can benefit from logic programming techniques.
|
|
| 3. |
- Bialek, Lukasz, et al.
(author)
-
A paraconsistent approach to actions in informationally complex environments
- 2019
-
In: Annals of Mathematics and Artificial Intelligence. - : SPRINGER. - 1012-2443 .- 1573-7470. ; 86:4, s. 231-255
-
Journal article (peer-reviewed)abstract
- Contemporary systems situated in real-world open environments frequently have to cope with incomplete and inconsistent information that typically increases complexity of reasoning and decision processes. Realistic modeling of such informationally complex environments calls for nuanced tools. In particular, incomplete and inconsistent information should neither trivialize nor stop both reasoning or planning. The paper introduces ACTLOG, a rule-based four-valued language designed to specify actions in a paraconsistent and paracomplete manner. ACTLOG is an extension of 4QL(Bel), a language for reasoning with paraconsistent belief bases. Each belief base stores multiple world representations. In this context, ACTLOGs action may be seen as a belief bases transformer. In contrast to other approaches, ACTLOG actions can be executed even when the underlying belief base contents is inconsistent and/or partial. ACTLOG provides a nuanced action specification tools, allowing for subtle interplay among various forms of nonmonotonic, paraconsistent, paracomplete and doxastic reasoning methods applicable in informationally complex environments. Despite its rich modeling possibilities, it remains tractable. ACTLOG permits for composite actions by using sequential and parallel compositions as well as conditional specifications. The framework is illustrated on a decontamination case study known from the literature.
|
|
| 4. |
- Boström, Henrik, et al.
(author)
-
Accelerating difficulty estimation for conformal regression forests
- 2017
-
In: Annals of Mathematics and Artificial Intelligence. - : Springer Netherlands. - 1012-2443 .- 1573-7470. ; 81:1-2, s. 125-144
-
Journal article (peer-reviewed)abstract
- The conformal prediction framework allows for specifying the probability of making incorrect predictions by a user-provided confidence level. In addition to a learning algorithm, the framework requires a real-valued function, called nonconformity measure, to be specified. The nonconformity measure does not affect the error rate, but the resulting efficiency, i.e., the size of output prediction regions, may vary substantially. A recent large-scale empirical evaluation of conformal regression approaches showed that using random forests as the learning algorithm together with a nonconformity measure based on out-of-bag errors normalized using a nearest-neighbor-based difficulty estimate, resulted in state-of-the-art performance with respect to efficiency. However, the nearest-neighbor procedure incurs a significant computational cost. In this study, a more straightforward nonconformity measure is investigated, where the difficulty estimate employed for normalization is based on the variance of the predictions made by the trees in a forest. A large-scale empirical evaluation is presented, showing that both the nearest-neighbor-based and the variance-based measures significantly outperform a standard (non-normalized) nonconformity measure, while no significant difference in efficiency between the two normalized approaches is observed. The evaluation moreover shows that the computational cost of the variance-based measure is several orders of magnitude lower than when employing the nearest-neighbor-based nonconformity measure. The use of out-of-bag instances for calibration does, however, result in nonconformity scores that are distributed differently from those obtained from test instances, questioning the validity of the approach. An adjustment of the variance-based measure is presented, which is shown to be valid and also to have a significant positive effect on the efficiency. For conformal regression forests, the variance-based nonconformity measure is hence a computationally efficient and theoretically well-founded alternative to the nearest-neighbor procedure.
|
|
| 5. |
- Cantwell, John, et al.
(author)
-
Probability, coherent belief and coherent belief changes
- 2019
-
In: Annals of Mathematics and Artificial Intelligence. - : Springer Netherlands. - 1012-2443 .- 1573-7470. ; 87, s. 259-291
-
Journal article (peer-reviewed)abstract
- This paper is about the statics and dynamics of belief states that are represented by pairs consisting of an agent’s credences (represented by a subjective probability measure) and her categorical beliefs (represented by a set of possible worlds). Regarding the static side, we argue that the latter proposition should be coherent with respect to the probability measure and that its probability should reach a certain threshold value. On the dynamic side, we advocate Jeffrey conditionalisation as the principal mode of changing one’s belief state. This updating method fits the idea of the Lockean Thesis better than plain Bayesian conditionalisation, and it affords a flexible method for adding and withdrawing categorical beliefs. We show that it fails to satisfy the traditional principles of Inclusion and Preservation for belief revision and the principle of Recovery for belief withdrawals, as well as the Levi and Harper identities. We take this to be a problem for the latter principles rather than for the idea of coherent belief change.
|
|
| 6. |
- Confalonieri, Roberto, et al.
(author)
-
Dealing with explicit preferences and uncertainty in answer set programming
- 2012
-
In: Annals of Mathematics and Artificial Intelligence. - Dordrecht : Springer Science and Business Media LLC. - 1012-2443 .- 1573-7470. ; 65:2-3, s. 159-198
-
Journal article (peer-reviewed)abstract
- In this paper, we show how the formalism of Logic Programs with Ordered Disjunction (LPODs) and Possibilistic Answer Set Programming (PASP) can be merged into the single framework of Logic Programs with Possibilistic Ordered Disjunction (LPPODs). The LPPODs framework embeds in a unified way several aspects of common-sense reasoning, nonmonotonocity, preferences, and uncertainty, where each part is underpinned by a well established formalism. On one hand, from LPODs it inherits the distinctive feature of expressing context-dependent qualitative preferences among different alternatives (modeled as the atoms of a logic program). On the other hand, PASP allows for qualitative certainty statements about the rules themselves (modeled as necessity values according to possibilistic logic) to be captured. In this way, the LPPODs framework supports a reasoning which is nonmonotonic, preference- and uncertainty-aware. The LPPODs syntax allows for the specification of (1) preferences among the exceptions to default rules, and (2) necessity values about the certainty of program rules. As a result, preferences and uncertainty can be used to select the preferred uncertain default rules of an LPPOD and, consequently, to order its possibilistic answer sets. Furthermore, we describe the implementation of an ASP-based solver able to compute the LPPODs semantics.
|
|
| 7. |
- Coquand, Thierry, 1961, et al.
(author)
-
Spectral schemes as ringed lattices
- 2009
-
In: ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE. - : Springer Science and Business Media LLC. - 1012-2443 .- 1573-7470. ; 56:3-4, s. 339-360
-
Journal article (peer-reviewed)
|
|
| 8. |
|
|
| 9. |
- Doherty, Patrick, 1957-, et al.
(author)
-
TALplanner : A temporal logic based forward chaining planner
- 2000
-
In: Annals of Mathematics and Artificial Intelligence. - : Springer. - 1012-2443 .- 1573-7470. ; 30:1-4, s. 119-169
-
Journal article (peer-reviewed)abstract
- We present TALplanner, a forward-chaining planner based on the use of domain-dependent search control knowledge represented as formulas in the Temporal Action Logic (TAL). TAL is a narrative based linear metric time logic used for reasoning about action and change in incompletely specified dynamic environments. TAL is used as the formal semantic basis for TALplanner, where a TAL goal narrative with control formulas is input to TALplanner which then generates a TAL narrative that entails the goal and control formulas. The sequential version of TALplanner is presented. The expressivity of plan operators is then extended to deal with an interesting class of resource types. An algorithm for generating concurrent plans, where operators have varying durations and internal state, is also presented. All versions of TALplanner have been implemented. The potential of these techniques is demonstrated by applying TALplanner to a number of standard planning benchmarks in the literature.
|
|
| 10. |
- Dunin-Keplicz, Barbara, et al.
(author)
-
Modeling and shadowing paraconsistent BDI agents
- 2023
-
In: Annals of Mathematics and Artificial Intelligence. - : SPRINGER. - 1012-2443 .- 1573-7470.
-
Journal article (peer-reviewed)abstract
- The Bdi model of rational agency has been studied for over three decades. Many robust multiagent systems have been developed, and a number of Bdi logics have been studied. Following this intensive development phase, the importance of integrating Bdi models with inconsistency handling and revision theory have been emphasized. There is also a demand for a tighter connection between Bdi-based implementations and Bdi logics. In this paper, we address these postulates by introducing a novel, paraconsistent logical Bdi model close to implementation, with building blocks that can be represented as Sql/rule-based databases. Importantly, tractability is achieved by reasoning as querying. This stands in a sharp contrast to the high complexity of known Bdi logics. We also extend belief shadowing, a shallow and lightweight alternative to deep and computationally demanding belief revision, to encompass agents motivational attitudes.
|
|
