Checking multi-agent schedules with temporal and causal information

Time management in a distributed multi-agent environment requires agents to progressively collaborate and negotiate before reaching a final feasible schedule of future events. In this process, it is important for individual agents to check whether a prototype schedule can meet their requirements and are free from undesirable effects in all possible event sequences. We present a modelling framework for encoding events with causal and temporal information. We show that the schedule validation task under this framework is NP-complete when the uncertainty in event ordering is very high. We develop a search algorithm for reasoning about possible consequences over a given set of events and show that the algorithm can effectively improve the computation efficiency by exploiting event-chain structure embedded in the time-interval information, which ends in tractable polynomial-time performance for events with moderate uncertainty in event ordering.