Abstract

Temporal reasoning problems occur in many application domains of Artificial Intelligence; therefore, it is important for us to develop algorithms for solving them efficiently. While some problems like Simple Temporal Problems are known to be tractable, some other problems like Disjunctive Temporal Problems are known to be NP-hard. In this paper, we provide a Linear Programming (LP) duality perspective on temporal reasoning problems. In many cases, we show that their LP duals are the commonly-studied flow problems in Graph Theory. Using the general theory of LP duality, we develop novel algorithms for efficiently solving several temporal reasoning problems. We also show that other previously-known efficient methods in temporal reasoning also fit into this perspective of LP duality.

Date

2018

Authors

TK Satish Kumar, Zhi Wang, Anoop Kumar, Craig Milo Rogers, Craig A Knoblock

Conference

ISAIM