{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:59:45Z","timestamp":1777715985654,"version":"3.51.4"},"reference-count":50,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[2023,3,28]],"date-time":"2023-03-28T00:00:00Z","timestamp":1679961600000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1453652, IIS-1849249, IIS-1849291"],"award-info":[{"award-number":["IIS-1453652, IIS-1849249, IIS-1849291"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>One important class of applications entails a robot scrutinizing, monitoring, or recording the evolution of an uncertain time-extended process. This sort of situation leads to an interesting family of active perception problems that can be cast as planning problems in which the robot is limited in what it sees and must, thus, choose what to pay attention to. The distinguishing characteristic of this setting is that the robot has influence over what it captures via its sensors, but exercises no causal authority over the process evolving in the world. As such, the robot\u2019s objective is to observe the underlying process and to produce a \u201cchronicle\u201d of occurrent events, subject to a goal specification of the sorts of event sequences that may be of interest. This paper examines variants of such problems in which the robot aims to collect sets of observations to meet a rich specification of their sequential structure. We study this class of problems by modeling a stochastic process via a variant of a hidden Markov model and specify the event sequences of interest as a regular language, developing a vocabulary of \u201cmutators\u201d that enable sophisticated requirements to be expressed. Under different suppositions on the information gleaned about the event model, we formulate and solve different planning problems. The core underlying idea is the construction of a product between the event model and a specification automaton. Using this product, we compute a policy that minimizes the expected number of steps to reach a goal state. We introduce a general algorithm for this problem as well as several more efficient algorithms for important special cases. The paper reports and compares performance metrics by drawing on some small case studies analyzed in depth via simulation. Specifically, we study the effect of the robot\u2019s observation model on the average time required for the robot to record a desired story. We also compare our algorithm with a baseline greedy algorithm, showing that our algorithm outperforms the greedy algorithm in terms of the average time to record a desired story. In addition, experiments show that the algorithms tailored to specialized variants of the problem are rather more efficient than the general algorithm.<\/jats:p>","DOI":"10.1177\/02783649211069154","type":"journal-article","created":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T09:18:35Z","timestamp":1648459115000},"page":"412-432","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":3,"title":["Planning to chronicle: Optimal policies for narrative observation of unpredictable events"],"prefix":"10.1177","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6342-2273","authenticated-orcid":false,"given":"Hazhar","family":"Rahmani","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of South Carolina, Columbia, SC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dylan A","family":"Shell","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Texas A&M University, College Station, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason M","family":"O\u2019Kane","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of South Carolina, Columbia, SC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2022,3,28]]},"reference":[{"key":"bibr1-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2021.103778"},{"key":"bibr2-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(65)90154-X"},{"key":"bibr3-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/5.5968"},{"key":"bibr4-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-017-9615-3"},{"key":"bibr5-02783649211069154","unstructured":"Bonet B, Geffner H (2003) Faster heuristic search algorithms for planning with uncertainty and full feedback. In: International joint conference on artificial intelligence, San Francisco, CA, United States, 9 August 2003, pp. 1233\u20131238."},{"key":"bibr6-02783649211069154","unstructured":"Bonet B, Geffner H (2009) Solving POMDPs: RTDP-Bel versus point-based algorithms. In: International joint conference on artificial intelligence, Pasadena, California, 11-17 July, 2009, pp. 1641\u20131646"},{"key":"bibr7-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00033-3"},{"key":"bibr8-02783649211069154","unstructured":"Boutilier C, Poole D (1996) Computing optimal policies for partially observable decision processes using compact representations. In: National conference on artificial intelligence, Citeseer, 04 August 1996, pp. 1168\u20131175."},{"key":"bibr9-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9562095"},{"key":"bibr10-02783649211069154","volume-title":"International symposium on distributed autonomous robotic systems","author":"Chaudhuri D","year":"2021"},{"key":"bibr11-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487754"},{"key":"bibr12-02783649211069154","unstructured":"Dai P, Goldsmith J (2007) Topological value iteration algorithm for Markov decision processes. In: International joint conference on artificial intelligence, Hyderabad, India, 6-12 January, 2007, pp. 1860\u20131865."},{"key":"bibr13-02783649211069154","unstructured":"Dibangoye JS, Shani G, Chaib-Draa B, et al. (2009) Topological order planner for POMDPs. In: Twenty-First international joint conference on artificial intelligence, Pasadena, California, 11-17 July 2009"},{"key":"bibr14-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224657"},{"key":"bibr15-02783649211069154","unstructured":"Gong B, Chao WL, Grauman K, et al. (2014) Diverse sequential subset selection for supervised video summarization. In: Advances in Neural Information Processing Systems. Cambridge, MA, United States, 8 December 2014, pp. 2069\u20132077."},{"key":"bibr16-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1000"},{"key":"bibr17-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10584-0_33"},{"key":"bibr18-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/TCSVT.2019.2904996"},{"key":"bibr19-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81688-9_28"},{"key":"bibr20-02783649211069154","unstructured":"Keyder E, Geffner H (2008) The HMDPP planner for planning with probabilities. In: Sixth international planning competition at ICAPS, Sydney, Australia, 14-18 September, 8."},{"key":"bibr21-02783649211069154","unstructured":"Kolobov AM, Weld DS (2010) Sixthsense: Fast and reliable recognition of dead ends in MDPs.In: Proceedings of the twenty-fourth AAAI conference on artificial intelligence, Atlanta, Georgia, USA, 11-15 July 2010."},{"key":"bibr22-02783649211069154","first-page":"438","volume-title":"Twenty-Eighth conference on uncertainty in artificial intelligence","author":"Kolobov A","year":"2012"},{"key":"bibr23-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.06.001"},{"key":"bibr24-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"bibr25-02783649211069154","doi-asserted-by":"crossref","unstructured":"Lee YJ, Ghosh J, Grauman K (2012) Discovering important people and objects for egocentric video summarization. In: IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, 16-21 June 2012, pp. 1346\u20131353.","DOI":"10.1109\/CVPR.2012.6247820"},{"issue":"8","key":"bibr26-02783649211069154","first-page":"707","volume":"10","author":"Levenshtein VI","year":"1966","journal-title":"Soviet Physics Doklady"},{"key":"bibr27-02783649211069154","unstructured":"Little I, Thi\u00e9baux S (2007) Probabilistic planning vs. replanning. In: ICAPS workshop on international planning competition: past, present and future, Providence, Rhode Island, United States, 22-26 September 2007."},{"key":"bibr28-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.350"},{"key":"bibr29-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/TBC.2019.2892585"},{"key":"bibr30-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1145\/3347713"},{"key":"bibr31-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.318"},{"key":"bibr32-02783649211069154","volume-title":"Clip-it! Language-Guided Video Summarization","author":"Narasimhan M","year":"2021"},{"key":"bibr33-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.118"},{"key":"bibr34-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"bibr35-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/IROS40897.2019.8968261"},{"key":"bibr36-02783649211069154","volume-title":"Algorithmic Foundations of Robotics (WAFR XIV)","author":"Rahmani H","year":"2020"},{"key":"bibr37-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2989"},{"key":"bibr38-02783649211069154","unstructured":"Robertson J, Young RM (2017) Narrative mediation as probabilistic planning. In: Thirteenth Artificial Intelligence and Interactive Digital Entertainment Conference, Snowbird, Little Cottonwood Canyon, Utah USA, 5-9 October 2017"},{"key":"bibr39-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2567"},{"key":"bibr40-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2015.11.009"},{"key":"bibr41-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/ECMR.2019.8870950"},{"key":"bibr42-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1007\/s10032-002-0082-8"},{"key":"bibr43-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-012-9200-2"},{"key":"bibr44-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8794450"},{"key":"bibr45-02783649211069154","first-page":"1772","volume":"26","author":"Somani A","year":"2013","journal-title":"Advances in Neural Information Processing Systems"},{"key":"bibr46-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.2.282"},{"key":"bibr47-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1145\/1198302.1198305"},{"key":"bibr48-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17452-0_23"},{"key":"bibr49-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5979827"},{"key":"bibr50-02783649211069154","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01237-3_24"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211069154","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649211069154","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211069154","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211069154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:04Z","timestamp":1777457824000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649211069154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,28]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.1177\/02783649211069154"],"URL":"https:\/\/doi.org\/10.1177\/02783649211069154","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,28]]}}}