{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,9]],"date-time":"2025-02-09T05:05:56Z","timestamp":1739077556776,"version":"3.37.0"},"reference-count":36,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2009,3,9]],"date-time":"2009-03-09T00:00:00Z","timestamp":1236556800000},"content-version":"unspecified","delay-in-days":4877,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotica"],"published-print":{"date-parts":[[1995,11]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>Planning a sequence of robot actions is especially difficult when the outcome of actions is uncertain, as is inevitable when interacting with the physical environment. In this paper we consider the case of finite state and action spaces where actions can be modeled as Markov transitions. Finding a plan that achieves a desired state with maximum probability is known to be an<jats:italic>NP-Complete<\/jats:italic>problem. We consider two algorithms: an exponential-time algorithm that maximizes probability, and a polynomial-time algorithm that maximizes a lower bound on the probability. As these algorithms trade off plan time for plan quality, we compare their performance on a mechanical system for orienting parts. Our results lead us to identify two properties of stochastic actions that can be used to choose between these planning algorithms for other applications.<\/jats:p>","DOI":"10.1017\/s0263574700018646","type":"journal-article","created":{"date-parts":[[2009,3,10]],"date-time":"2009-03-10T13:12:28Z","timestamp":1236690748000},"page":"565-573","source":"Crossref","is-referenced-by-count":3,"title":["Comparing two algorithms for automatic planning by robots in stochastic environments"],"prefix":"10.1017","volume":"13","author":[{"given":"Alan D.","family":"Christiansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenneth Y.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,3,9]]},"reference":[{"key":"S0263574700018646_ref025","doi-asserted-by":"publisher","DOI":"10.1177\/027836498800700303"},{"volume-title":"Heuristics: Intelligent Search Strategies for Computer Problem Solving","year":"1984","author":"Pearl","key":"S0263574700018646_ref034"},{"key":"S0263574700018646_ref024","doi-asserted-by":"publisher","DOI":"10.1177\/027836498800700101"},{"key":"S0263574700018646_ref022","unstructured":"22. Christiansen A.D. , \u201cAutomatic Acquisition of Task Theories for Robotic Manipulation\u201d PhD thesis (Carnegie Mellon University, School of Computer Science, 03 1992)."},{"key":"S0263574700018646_ref029","unstructured":"29. Taylor R.H. , Mason M.T. and Goldberg K.Y. , \u201cSensorbased manipulation planning as a game with nature\u201d International Symposium on Robotics Research (August, 1987) pp. 421\u2013429."},{"key":"S0263574700018646_ref026","doi-asserted-by":"publisher","DOI":"10.1109\/56.9297"},{"key":"S0263574700018646_ref014","doi-asserted-by":"crossref","DOI":"10.21236\/ADA254568","volume-title":"Planning and Control","author":"Dean","year":"1991"},{"key":"S0263574700018646_ref028","doi-asserted-by":"publisher","DOI":"10.1109\/56.800"},{"volume-title":"Technical Report UCB\/CSD 88\/435","year":"1988","author":"Russell","key":"S0263574700018646_ref009"},{"key":"S0263574700018646_ref010","unstructured":"10. Cheeseman P. \u201cIn defense of probability\u201d Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, CA, IJCAI (August 1985) pp. 1002\u20131009."},{"volume-title":"Probabilistic Reasoning in Intelligent Systems","year":"1988","author":"Pearl","key":"S0263574700018646_ref008"},{"key":"S0263574700018646_ref027","unstructured":"27. Brost R.C. , \u201cAnalysis and Planning of Planar Manipulation Tasks\u201d PhD thesis (Carnegie Mellon University, School of Computer Science, 01 1991)."},{"key":"S0263574700018646_ref007","doi-asserted-by":"publisher","DOI":"10.1207\/s15516709cog0102_2"},{"key":"S0263574700018646_ref033","unstructured":"33. Goldberg K.Y. , \u201cStochastic Plans for Robotic Manipulation\u201d PhD thesis (Garnegie Mellon University, School of Computer Science, 08 1990)."},{"key":"S0263574700018646_ref017","unstructured":"17. Dufay B. and Latombe J. C. , \u201cAn approach to automatic robot programming based on inductive learning\u201d International Symposium on Robotics Research (1983) pp. 97\u2013115."},{"key":"S0263574700018646_ref019","doi-asserted-by":"publisher","DOI":"10.1109\/70.88023"},{"key":"S0263574700018646_ref021","doi-asserted-by":"crossref","unstructured":"21. Bennett S. and DeJong G. , \u201cComparing stochastic planning to the acquisition of increasingly permissive plans for complex, uncertain domains\u201d International Workshop on Machine Learning (06 1991) pp. 586\u2013590.","DOI":"10.1016\/B978-1-55860-200-7.50119-7"},{"volume-title":"Technical Report COINS 89-89","year":"1989","author":"Barto","key":"S0263574700018646_ref018"},{"key":"S0263574700018646_ref015","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1982.1103060"},{"key":"S0263574700018646_ref012","unstructured":"12. Etzioni O. , \u201cTractable decicion-analytic control\u201d Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, Los Altos, California (1989) (Morgan Kaufmann, San Mateo, 1989). An expanded version is available as technical report CMU-CS-89\u2013119."},{"key":"S0263574700018646_ref020","unstructured":"20. Gross K.P. . \u201cConcept Acquisition through Attribute Evolution and Experimentation\u201d PhD thesis (Carnegie Mellon University, School of Computer Science, 05 1991)."},{"volume-title":"Dynamic Programming: Deterministic and Stochastic Models","year":"1987","author":"Bertsekas","key":"S0263574700018646_ref013"},{"key":"S0263574700018646_ref011","doi-asserted-by":"publisher","DOI":"10.2307\/1884852"},{"volume-title":"Optimal Statistical Decisions","year":"1970","author":"DeGroot","key":"S0263574700018646_ref002"},{"key":"S0263574700018646_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4286-2"},{"volume-title":"Learning Automata: An Introduction","year":"1988","author":"Narendra","key":"S0263574700018646_ref016"},{"key":"S0263574700018646_ref030","doi-asserted-by":"crossref","unstructured":"30. Christiansen A.D. , \u201cManipulation planning from empirical backprojections\u201d IEEE International Conference on Robotics and Automation (April, 1991) pp. 762\u2013768.","DOI":"10.1109\/ROBOT.1991.131678"},{"key":"S0263574700018646_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-6746-2"},{"key":"S0263574700018646_ref023","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500303"},{"key":"S0263574700018646_ref031","doi-asserted-by":"publisher","DOI":"10.1016\/0921-8890(91)90011-9"},{"key":"S0263574700018646_ref032","doi-asserted-by":"crossref","unstructured":"32. Christiansen A.D. , \u201cLearning to predict in uncertain continuous tasks\u201d International Conference on Machine Learning (July, 1992) pp. 72\u201381.","DOI":"10.1016\/B978-1-55860-247-2.50015-2"},{"volume-title":"Dynamic Probabilistic Systems (2 volumes)","year":"1971","author":"Howard","key":"S0263574700018646_ref004"},{"key":"S0263574700018646_ref035","unstructured":"35. Wilson R. and Latombe J. C. , \u201cOn the qualitative structure of a mechanical assembly\u201d National Conference on Artificial Intelligence (1992) pp. 697\u2013702."},{"key":"S0263574700018646_ref036","unstructured":"36. Erdmann M.A. , \u201cOn Probabilistic Strategies for Robot Tasks\u201d PhD. thesis (MIT, Cambridge, MA, 1989)."},{"key":"S0263574700018646_ref006","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.441"},{"key":"S0263574700018646_ref001","doi-asserted-by":"crossref","unstructured":"1. Astrom K.J. , \u201cAdaptive feedback control.\u201d Proceedings of the IEEE 75(2) 185\u2013217 (1987).","DOI":"10.1109\/PROC.1987.13721"}],"container-title":["Robotica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0263574700018646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T04:54:21Z","timestamp":1738990461000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0263574700018646\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,11]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1995,11]]}},"alternative-id":["S0263574700018646"],"URL":"https:\/\/doi.org\/10.1017\/s0263574700018646","relation":{},"ISSN":["0263-5747","1469-8668"],"issn-type":[{"type":"print","value":"0263-5747"},{"type":"electronic","value":"1469-8668"}],"subject":[],"published":{"date-parts":[[1995,11]]}}}