Abstract-Conditional Simple Temporal Network (CSTN) är en begränsningsbaserad graf-formalism för villkorlig tidsplanering. Tre begrepp om konsekvens uppstår för CSTN och CSTP: svaga, starka och dynamiska. Dynamisk överensstämmelse (DC) är den mest intressanta idén, men det är också den mest utmanande. För att ta itu med problemet med DC-kontroll införde vi [5] ε-DC (en förfinad, mer realistisk bild av DC) och gav den en algoritmisk lösning. Därefter, med tanke på att DC innebär ε-DC för några tillräckligt små ε > 0, och att för varje ε > 0 den innehar att ε-DC innebär DC, erbjöd vi en skarp lägre begränsande analys av det kritiska värdet av reaktionstidenε under vilken de två begreppen sammanfaller. Detta levererade den första (pseudo) ensamexponentiella tid algoritmen för DC-kontroll av CSTNs. Men ε-DC-begreppet är intressant i sig, och ε-DCChecking algoritmen i [5] bygger på antagandet att reaktionstiden uppfyller ε > 0; lämnar olöst frågan om vad som händer när ε = 0. I detta arbete introducerar och studerar vi π-DC, en sund uppfattning om DC med en omedelbar reaktionstid (dvs. en där planeraren kan reagera på alla observationer vid samma tidpunkt då observationen görs). För det första visar vi genom ett motexempel att π-DC inte motsvarar 0-DC, och att 0-DC faktiskt är otillräckligt för att modellera DC med en omedelbar reaktionstid. Detta visar att de viktigaste resultaten i vårt tidigare arbete inte gäller direkt, som de formulerades, fallet ε = 0. Motiverade av denna iakttagelse, som ett andra bidrag, våra tidigare verktyg utvidgas för att hantera π-DC, och begreppet ps-tree introduceras, också peka på ett förhållande mellan π-DC och HyTN-Consistency. För det tredje identifieras en enkel minskning från π-DC till DC. Detta gör det möjligt för oss att designa och analysera den första ljud-och-fullständiga π-DC-kontrollproceduren. Anmärkningsvärt nog förblir tidskomplexiteten hos den föreslagna algoritmen (pseudo) ensamexponentiell i antalet propositionsbokstäver.
I REF introduceras och studeras slutligen π-DC, ett sunt begrepp om dynamisk överensstämmelse med en omedelbar reaktionstid, dvs. en tidpunkt då Planner får reagera på varje observation vid samma tidpunkt då observationen görs.
Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks
{'venue': '2016 23rd International Symposium on Temporal Representation and Reasoning (TIME)', 'journal': '2016 23rd International Symposium on Temporal Representation and Reasoning (TIME)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}