Skip to main content
Skip to article control options
No AccessFull-Length Papers

Property-Based Brittleness Analysis of Temporal Networks

Published Online:https://doi.org/10.2514/1.I011189

A new framework is proposed to analyze the brittleness of task networks with respect to an arbitrary set of user-specified properties, such as dynamic controllability or minimum battery state of charge of a rover. The proposed algorithms allow the detection and enumeration of activities that, with modest task execution duration variation, make the success of execution no longer guaranteed in terms of the given set of properties. A metric for measuring an activity’s brittleness, defined as the degree of acceptable deviation from its nominal duration that preserves the desired user-specified properties, is introduced and how that measurement is mapped to task network structure is described. Complementary to existing work on temporal robustness analysis, which informs how likely a task network is to succeed or not under temporal controllability constraints, the new analysis and metric not only generalize robustness analysis to a set of user-defined properties (as opposed to strong or dynamic controllability, for instance), but they also go deeper to pinpoint the sources of potential brittleness. An analyzer is developed, which helps human designers and/or automated task network generators focus on and address sources of undesirable brittleness. The approach is applied in Mars rover and biomanufacturing operations scenarios.

References

  • [1] Rabideau G. and Benowitz E., “Prototyping an Onboard Scheduler for the Mars 2020 Rover,” International Workshop on Planning and Scheduling for Space, 2017, pp. 1–9. Google Scholar

  • [2] Chi W., Chien S., Agrawal J., Rabideau G., Benowitz E., Gaines D., Fosse E., Kuhn S. and Biehl J., “Embedding a Scheduler in Execution for a Planetary Rover,” Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, 2018, pp. 312–320. Google Scholar

  • [3] Gaines D., Doran G., Justice H., Rabideau G., Schaffer S., Verma V., Wagstaff K., Vasavada V., Huffman W., Anderson R., Mackey R. and Estlin T., “Productivity Challenges for Mars Rover Operations: A Case Study of Mars Science Laboratory Operations,” Jet Propulsion Lab. TR D-97908, 2016. Google Scholar

  • [4] Santana P., Vaquero T., Toledo C., Wang A., Fang C. and Williams B., “PARIS: A Polynomial-Time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty,” Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling, 2016, pp. 267–275. Google Scholar

  • [5] Akmal S., Ammons S., Li H. and Boerkoel J. C., “Quantifying Degrees of Controllability in Temporal Networks with Uncertainty,” Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, 2019, pp. 22–30. Google Scholar

  • [6] Vaquero T., Chien S., Agrawal J., Chi W. and Huntsberger T., “Temporal Brittleness Analysis of Task Networks for Planetary Rovers,” Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, 2019, pp. 564–572. Google Scholar

  • [7] Cui J., Yu P., Fang C., Haslum P. and Williams B. C., “Optimising Bounds in Simple Temporal Networks with Uncertainty Under Dynamic Controllability Constraints,” Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling, 2015, pp. 52–60. Google Scholar

  • [8] Mars 2020 Rover Mission,” 2018, https://mars.nasa.gov/mars2020 [retrieved 18 Aug. 2022]. Google Scholar

  • [9] Agrawal J., Chi W., Chien S., Rabideau G., Kuhn S. and Gaines D., “Enabling Limited Resource-Bounded Disjunction in Scheduling,” Proceedings of the Eleventh International Workshop on Planning and Scheduling for Space, 2019, pp. 7–15; also 29th International Conference on Automated Planning and Scheduling (ICAPS) Workshop PlanRob 2019 and ICAPS SPARK 2019 and ICAPS IntEx 2019. Google Scholar

  • [10] Dechter R., Meiri I. and Pearl J., “Temporal Constraint Networks,” Artificial Intelligence, Vol. 49, Nos. 1–3, 1991, pp. 61–95. https://doi.org/10.1016/0004-3702(91)90006-6 CrossrefGoogle Scholar

  • [11] Vidal T. and Ghallab M., “Dealing with Uncertain Durations in Temporal Constraint Networks Dedicated to Planning,” European Conference on Artificial Intelligence, edited by Wahlster W., 1996, pp. 48–54. Google Scholar

  • [12] Tsamardinos I., “A Probabilistic Approach to Robust Execution of Temporal Plans with Uncertainty,” Methods and Applications of Artificial Intelligence, edited by Vlahavas I. P. and Spyropoulos C. D., Springer, Berlin, 2002, pp. 97–108. CrossrefGoogle Scholar

  • [13] Fang C., Yu P. and Williams B. C., “Chance-Constrained Probabilistic Simple Temporal Problems,” Proceedings of the Twenty-Eighth Conference on Artificial Intelligence, AAAI Press, 2014, pp. 2264–2270. Google Scholar

  • [14] Brooks J., Reed E., Gruver A. and Boerkoel J. C., “Robustness in Probabilistic Temporal Planning,” Proceedings of the Twenty-Nineth Conference on Artificial Intelligence, AAAI Press, 2015, pp. 3239–3246. Google Scholar

  • [15] Wallace R. J. and Freuder E. C., “Dispatchable Execution of Schedules Involving Consumable Resources,” Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, AAAI Press, 2000, pp. 283–290. Google Scholar

  • [16] Laborie P., “Resource Temporal Networks: Definition and Complexity,” Proceedings of the Eighth International Joint Conference on Artificial Intelligence, Morgan Kaufmann, San Francisco, CA, 2003, pp. 948–953. Google Scholar

  • [17] Sidor S., Yu P., Fang C. and Williams B. C., “Time Resource Networks,” Computing Research Repository, Vol. abs/1602.03203, 2016, pp. 1–7. Google Scholar

  • [18] Kumar T. K. S., Wang Z., Kumar A., Rogers C. M. and Knoblock C. A., “Load Scheduling of Simple Temporal Networks Under Dynamic Resource Pricing,” Proceedings of the Thirty-Second Conference on Artificial Intelligence, AAAI Press, 2018, pp. 6227–6236. Google Scholar

  • [19] Huguet M. J., Lopez P. and Vidal T., “Dynamic Task Sequencing in Temporal Problems with Uncertainty,” Proceedings of the Workshop on On-Line Planning and Scheduling in Sixth International Conference on AI Planning & Scheduling, 2002, pp. 41–48. Google Scholar

  • [20] Combi C., Posenato R., Viganò L. and Zavatteri M., “Conditional Simple Temporal Networks with Uncertainty and Resources,” Artificial Intelligence Research, Vol. 64, No. 1, 2019, pp. 931–985. https://doi.org/10.1613/jair.1.11453 Google Scholar

  • [21] Vidal T. and Fargier H., “Handling Contingency in Temporal Constraint Networks: From Consistency to Controllabilities,” Experimental and Theoretical Artificial Intelligence, Vol. 11, No. 1, 1999, pp. 23–45. CrossrefGoogle Scholar

  • [22] Saint-Guillain M., Stegun Vaquero T., Chien S. and Abrahams J., “Probabilistic Temporal Networks with Ordinary Distributions: Theory, Robustness and Expected Utility,” Artificial Intelligence Research, Vol. 71, Aug. 2021, pp. 1091–1136. CrossrefGoogle Scholar

  • [23] Morris P., Muscettola N. and Vidal T., “Dynamic Control of Plans with Temporal Uncertainty,” Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, Vol. 1, Morgan Kaufmann, San Francisco, CA, 2001, pp. 494–499. Google Scholar

  • [24] Morris P., “Dynamic Controllability and Dispatchability Relationships,” International Conference on Artificial Intelligence and Operational Research Techniques in Constraint Programming for Combinatorial Optimization Problems, Vol. 8451, Lecture Notes in Computer Science, Springer, 2014, pp. 464–479. Google Scholar

  • [25] Cesta A., Oddi A. and Smith S. F., “Profile-Based Algorithms to Solve Multiple Capacitated Metric Scheduling Problems,” Proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems, 1998, pp. 214–223. Google Scholar

  • [26] Wilson M., Klos T., Witteveen C. and Huisman B., “Flexibility and Decoupling in Simple Temporal Networks,” Artificial Intelligence, Vol. 214, Sept. 2014, pp. 26–44. https://doi.org/10.1016/j.artint.2014.05.003 CrossrefGoogle Scholar

  • [27] Lund K., Dietrich S., Chow S. and Boerkoel J. C., “Robust Execution of Probabilistic Temporal Plans,” Proceedings of the Twenty-First Conference on Artificial Intelligence, AAAI Press, 2017, pp. 3597–3604. Google Scholar

  • [28] Huang A., Lloyd L., Omar M. and Boerkoel J. C., “New Perspectives on Flexibility in Simple Temporal Planning,” Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, 2018, pp. 123–131. Google Scholar

  • [29] Lee J. Y., Ojha V. and Boerkoel J. C., “Measuring and Optimizing Durability Against Scheduling Disturbances,” Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, 2019, pp. 264–268. Google Scholar

  • [30] Saint-Guillain M., “Robust Operations Management on Mars,” Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, 2019, pp. 368–376. Google Scholar

  • [31] Saint-Guillain M., Stegun Vaquero T., Agrawal J. and Chien S., “Robustness Computation of Dynamic Controllability in Probabilistic Temporal Networks with Ordinary Distributions,” Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, edited by Bessiere C., International Joint Conferences on Artificial Intelligence Organization, 2020, pp. 4168–4175. https://doi.org/10.24963/ijcai.2020/576 Google Scholar

  • [32] Stoskov Y., “Stability of an Optimal Schedule,” European Journal of Operational Research, Vol. 55, No. 1, 1991, pp. 91–102. https://doi.org/10.1016/0377-2217(91)90194-Z CrossrefGoogle Scholar

  • [33] Ali S., Maciejewski A. A., Siegel H. J. and Kim J.-K., “Definition of Robustness Metric for Resource Allocation,” Proceedings of the Seventeenth International Parallel and Distributed Processing Symposium, IEEE, New York, 2003, pp. 1–10. https://doi.org/10.1109/IPDPS.2003.1213128 Google Scholar

  • [34] Hall N. G. and Posner M. E., “Sensitivity Analysis for Scheduling Problems,” Journal of Scheduling, Vol. 7, No. 1, 2004, pp. 49–83. https://doi.org/10.1023/B:JOSH.0000013055.31639.f6 CrossrefGoogle Scholar

  • [35] Bit-Monnot A., “Temporal and Hierarchical Models for Planning and Acting in Robotics,” Ph.D. Thesis, LAAS-CNRS, Toulouse, France, 2016. Google Scholar

  • [36] Dvorák F., Barták R., Bit-Monnot A., Ingrand F. and Ghallab M., “Planning and Acting with Temporal and Hierarchical Decomposition Models,” Proceedings of the Twenty-Sixth International Conference on Tools with Artificial Intelligence, IEEE, New York, 2014, pp. 115–121. https://doi.org/10.1109/ICTAI.2014.27 Google Scholar

  • [37] Nilsson M., Kvarnström J. and Doherty P., “Planning with Temporal Uncertainty, Resources and Non-Linear Control Parameters,” Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, AAAI Press, Delft, The Netherlands, 2018, pp. 180–189. Google Scholar

  • [38] Abrahams J. R., Chu D. A., Diehl G., Knittel M., Lin J., Lloyd W., Boerkoel J. C. and Jeremy F., “Dream: An Algorithm for Mitigating the Overhead of Robust Rescheduling,” Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 29, 2019, pp. 3–12. Google Scholar

  • [39] Umbrico A., Cesta A., Mayer M. C. and Orlandini A., “Integrating Resource Management and Timeline-Based Planning,” Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, edited by de Weerdt M., Koenig S., Röger G. and Spaan M. T. J., AAAI Press, 2018, pp. 264–272. Google Scholar

  • [40] Shapiro A., Dentcheva D. and Ruszczynski A., Lectures on Stochastic Programming: Modeling and Theory, Soc. for Industrial and Applied Mathematics, 2021. CrossrefGoogle Scholar

  • [41] Cimatti A., Micheli A. and Roveri M., “Dynamic Controllability of Disjunctive Temporal Networks: Validation and Synthesis of Executable Strategies,” Proceedings of the Thirtieth Conference on Artificial Intelligence, AAAI Press, 2016, pp. 3116–3122. Google Scholar

  • [42] Lenstra J. K. and Kan A. H. G. R., “Computational Complexity of Discrete Optimization Problems,” Annals of Discrete Mathematics, Vol. 4, Jan. 1979, pp. 121–140. CrossrefGoogle Scholar

  • [43] Yu P., Fang C. and Williams B., “Resolving Over-Constrained Probabilistic Temporal Problems Through Chance Constraint Relaxation,” Proceedings of the Twenty-Ninth Conference on Artificial Intelligence, AAAI Press, 2015, pp. 3425–3431. Google Scholar

  • [44] Michel L. and Hentenryck P. V., “Iterative Relaxations for Iterative Flattening in Cumulative Scheduling,” Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling, 2004, pp. 200–208. Google Scholar