A Geometric Dynamic Temporal Reasoning Method with Tags for Cognitive Systems

A Geometric Dynamic Temporal Reasoning Method with Tags for Cognitive Systems

Rui Xu (Beijing Institute of Technology, China), Zhaoyu Li (Beijing Institute of Technology, China), Pingyuan Cui (Beijing Institute of Technology, China), Shengying Zhu (Beijing Institute of Technology, China) and Ai Gao (Beijing Institute of Technology, China)
DOI: 10.4018/978-1-7998-0951-7.ch013


Temporal reasoning is one of the cognitive capabilities humans involve in communicating with others and everything appears related because of temporal reference. Therefore, in this paper a geometric dynamic temporal reasoning algorithm is proposed to solve the temporal reasoning problem, especially in autonomous planning and scheduling. This method is based on the representation of actions in a two dimensional coordination system. The main advantage of this method over others is that it uses tags to mark new constraints added into the constraint network, which leads the algorithm to deal with pending constraints rather than all constraints. This characteristic makes the algorithm suitable for temporal reasoning, where variables and constraints are always added dynamically. This algorithm can be used not only in intelligent planning, but also computational intelligence, real-time systems, and etc. The results show the efficiency of our algorithm from four cases simulating the planning and scheduling process.
Chapter Preview

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).

Complete Chapter List

Search this Book: