A Geometric Dynamic Temporal Reasoning Method with Tags for Cognitive Systems

1. Introduction

The notion of time is obvious in any activity that requires intelligence (Pani & Bhattacharjee, 2001; Wang, 2014). The temporal reasoning is one of the cognitive capabilities humans involve in communicating with others (Stock, 1998). Everything appears related because of temporal reference (Pani & Bhattacharjee, 2001). Therefore, cognitive models or intelligent systems have to be developed to mode this capability of representing time and reasoning about temporal relationship (Stracuzzi, Li, Cleveland, & Langley, 2009; Wang & Patel, 2009). Certainly, it is also important many possible application of computer-based systems, for instance planning actions in the real world which is one of high cognitive abilities, scheduling within a complex system (Cervantes, Rodríguez, López, Ramos, & Robles, 2013; Stock, 1998).

This paper takes the application of temporal representation and reasoning in autonomous planning and scheduling as an example to specify our work, because concepts about time are very important when people are talking about actions or events. In real world, actions are not instantaneous but have start times, end times and durations. An important challenge in current planning and scheduling research is time dimension management to allow for the simultaneous execution of non-instantaneous actions (M. C. Cooper, Maris, & Régnier, 2013). The sequential nature of classical plans is often too restrictive to cope with a temporal plan that consists of a set of instances of durative actions (M. Cooper, Maris, & Régnier, 2014). Therefore, time and temporal constraints must be considered in planning and scheduling methods.

Plan-space planning is well suited to temporal planning problems (Cushing, 2012). In plan-space planning, temporal reasoning is needed to check whether a simple temporal problem (STP) instance is consistent once a flaw and conflict is solved (Barták, Morris, & Venable, 2014). It means the temporal reasoning algorithm is called for many times. So improving the efficiency of temporal reasoning in dynamic environment can make the performance of the planning and scheduling method better. Therefore, the authors are interested in dynamic reasoning, namely whenever a new constraint or variable is asserted, this paper wants to maintain a solution of the STP rather than recomputing it using a “static” algorithm (Gerevini, 2005). The static algorithm, such as the Floyd-Warshall algorithm (Aini & Salehipour, 2012), leads to computation cost, because when the value of local variables changes or a variable/constraint is added to an STN, the whole network needs to be propagated again (Xu, 2004).

The most commonly used method is based on a simple temporal network (STN) and there is a list of algorithms. Xu et al. (2004) has proposed a dynamic algorithm which only computes the partial network influenced by the new introduced constraint rather than the whole network with the worst time complexity of the algorithm. Mouhoub and Yip (2002) presented a comparative study of dynamic arc-consistent algorithms in the case of temporal constraint problems and shown the efficiency of AC-3.1|DC algorithm. Planken et al. (2010) presented a brief survey of existing incremental algorithms and proposed a new algorithm that incrementally enforces partial path consistency. Gerevini (2005) proposed a collection of new polynomial algorithms to incrementally decide satisfiability, to maintain a solution, or to update the minimal representation of the CSP. This approach based on STN also has been used in several planning and scheduling systems in order to solve real-world problems, such as the Heuristic Scheduling Testbed System of Deep Space 1 (Muscettola, 1994), the EUROPA system (Barreiro et al., 2012; Bresina, 2015; Iwig et al., 2015), IxTeT (Lemai, 2004) and VHPOP (Younes & Simmons, 2003).