To Örebro University

oru.seÖrebro University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Simple Temporal Problems with Taboo Regions
University of Southern California, Los Angeles, USA. (Computer Science Department)
Örebro University, School of Science and Technology. (AASS)
University of Southern California, Los Angeles, USA. (Computer Science Department)
2013 (English)In: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2013Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we define and study the general framework of Simple Temporal Problems with Taboo regions (STPTs) and show how these problems capture metric temporal reasoning aspects which are common to many real-world applications. STPTs encode simple temporal constraints between events and user-defined taboo regions on the timeline, during which no event is allowed to take place. We discuss two different variants of STPTs. The first one deals with (instantaneous) events, while the second one allows for (durative) processes. We also provide polynomial-time algorithms for solving them. If all events or processes cannot be scheduled outside of the taboo regions, one needs to define and reason about "soft" STPTs. We show that even "soft" STPTs can be solved in polynomial time, using reductions to max-flow problems. The resulting algorithms allow for incremental computations, which is important for the successful application of our approach in real-time domains.

Place, publisher, year, edition, pages
AAAI Press, 2013.
Keywords [en]
Temporal Reasoning, Constraint Satisfaction, Algorithms and Complexity
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:oru:diva-29945OAI: oai:DiVA.org:oru-29945DiVA, id: diva2:635099
Conference
Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI), July 16-18, 2013, Bellevue, Washington, USA
Funder
Knowledge Foundation, SAUNAAvailable from: 2013-07-02 Created: 2013-07-02 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

PDF

Authority records

Cirillo, Marcello

Search in DiVA

By author/editor
Cirillo, Marcello
By organisation
School of Science and Technology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 251 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf