Thumbnail
Access Restriction
Open

Author Nilsson, Mikael ♦ Kvarnström, Jonas ♦ Doherty, Patrick
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Incremental Dynamic Controllability ♦ Fastidc Algorithm Achieves ♦ Uncontrollable Network ♦ Controllable Executable Regardless ♦ Plan Construction ♦ Temporal Problem ♦ Dispatchable Form ♦ New Constraint ♦ Simple Temporal Network ♦ Uncontrollable Duration
Abstract Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are determined by nature, as is often the case for actions in planning. As such networks are generated it is essential to verify that they are dynamically controllable – executable regardless of the outcomes of uncontrollable durations – and to convert them to a dispatchable form. The previously published FastIDC algorithm achieves this incrementally and can therefore be used efficiently during plan construction. In this paper we show that FastIDC is not sound when new constraints are added, sometimes labeling networks as dynamically controllable when they are not. We analyze the algorithm, pinpoint the cause, and show how the algorithm can be modified to correctly detect uncontrollable networks.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article