Reasoning about Actions with Sensing under Qualitative and Probabilistic Uncertainty

被引:15
|
作者
Iocchi, Luca [1 ]
Lukasiewicz, Thomas [2 ]
Nardi, Daniele [1 ]
Rosati, Riccardo [1 ]
机构
[1] Sapienza Univ Roma, DIS, I-00185 Rome, Italy
[2] Univ Oxford, Comp Lab, Oxford OX1 3QD, England
基金
奥地利科学基金会;
关键词
Algorithms; Languages; Reasoning about actions; sensing; qualitative and probabilistic uncertainty; action languages; description logics; imprecise probabilities; LOGIC; KNOWLEDGE; AGENTS;
D O I
10.1145/1459010.1459015
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We focus on the aspect of sensing in reasoning about actions under qualitative and probabilistic uncertainty. We first define the action language E for reasoning about actions with sensing, which has a semantics based on the autoepistemic description logic ALCK(NF), and which is given a formal semantics via a system of deterministic transitions between epistemic states. As an important feature, the main computational tasks in E can be done in linear and quadratic time. We then introduce the action language epsilon+ for reasoning about actions with sensing under qualitative and probabilistic uncertainty, which is an extension of E by actions with nondeterministic and probabilistic effects, and which is given a formal semantics in a system of deterministic, nondeterministic, and probabilistic transitions between epistemic states. We also define the notion of a belief graph, which represents the belief state of an agent after a sequence of deterministic, nondeterministic, and probabilistic actions, and which compactly represents a set of unnormalized probability distributions. Using belief graphs, we then introduce the notion of a conditional plan and its goodness for reasoning about actions under qualitative and probabilistic uncertainty. We formulate the problems of optimal and threshold conditional planning under qualitative and probabilistic uncertainty, and show that they are both uncomputable in general. We then give two algorithms for conditional planning in our framework. The first one is always sound, and it is also complete for the special case in which the relevant transitions between epistemic states are cycle-free. The second algorithm is a sound and complete solution to the problem of finite-horizon conditional planning in our framework. Under suitable assumptions, it computes every optimal finite-horizon conditional plan in polynomial time. We also describe an application of our formalism in a robotic-soccer scenario, which underlines its usefulness in realistic applications.
引用
收藏
页数:41
相关论文
共 50 条
  • [1] Reasoning about actions with sensing under qualitative and probabilistic uncertainty
    Iocchi, L
    Lukasiewicz, T
    Nardi, D
    Rosati, R
    ECAI 2004: 16TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2004, 110 : 818 - 822
  • [2] Reasoning about actions under uncertainty: A possibilistic approach
    Carlos Nieves, Juan
    Osorio, Mauricio
    Cortes, Ulises
    Caballero, Francisco
    Lopez-Navidad, Antonio
    ARTIFICIAL INTELLIGENCE RESEARCH AND DEVELOPMENT, 2007, 163 : 300 - +
  • [3] Reasoning about Actions in a Probabilistic Setting
    Baral, C
    Tran, N
    Tuan, LC
    EIGHTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-02)/FOURTEENTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE (IAAI-02), PROCEEDINGS, 2002, : 507 - 512
  • [4] Probabilistic Logic for Reasoning About Actions in Time
    Dautovic, Sejla
    Doder, Dragan
    SYMBOLIC AND QUANTITATIVE APPROACHES TO REASONING WITH UNCERTAINTY, ECSQARU 2019, 2019, 11726 : 385 - 396
  • [6] Enrichment of qualitative beliefs for reasoning under uncertainty
    Li, Xinde
    Huang, Xinhan
    Dezert, Jean
    Smarandache, Florentin
    2007 PROCEEDINGS OF THE 10TH INTERNATIONAL CONFERENCE ON INFORMATION FUSION, VOLS 1-4, 2007, : 1595 - +
  • [7] Qualitative reasoning under uncertainty with symbolic probabilities
    Pacholczyk, Daniel
    Hunault, Gilles
    Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science), 1996, 1137
  • [8] Information relevance and qualitative reasoning under uncertainty
    Chachoua, M
    Pacholczyk, D
    IC-AI'2000: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 1-III, 2000, : 1045 - 1051
  • [9] Dynamic Reasoning under Probabilistic Uncertainty in the Semantic Web
    Chen, Limin
    Shi, Zhongzhi
    INTELLIGENT COMPUTING AND INFORMATION SCIENCE, PT I, 2011, 134 (0I): : 341 - 347
  • [10] Reasoning about (Negative) Trust under Uncertainty
    Doneda, Francesca
    Genco, Francesco A.
    Primiero, Giuseppe
    TWENTY YEARS OF THEORETICAL AND PRACTICAL SYNERGIES, CIE 2024, 2024, 14773 : XXX - XXX