Planning for human-robot teaming in open worlds

Abstract

As the number of applications for human-robot teaming continue to rise, there is an increasing need for planning technologies that can guide robots in such teaming scenarios. In this article, we focus on adapting planning technology to Urban Search And Rescue (USAR) with a human-robot team. We start by showing that several aspects of state-of-the-art planning technology, including temporal planning, partial satisfaction planning, and replanning, can be gainfully adapted to this scenario. We then note that human-robot teaming also throws up an additional critical challenge, namely, enabling existing planners, which work under closed-world assumptions, to cope with the open worlds that are characteristic of teaming problems such as USAR. In response, we discuss the notion of conditional goals, and describe how we represent and handle a specific class of them called open world quantified goals. Finally, we describe how the planner, and its open world extensions, are integrated into a robot control architecture, and provide an empirical evaluation over USAR experimental runs to establish the effectiveness of the planning components.

References

1. Agre, P. and Chapman, D. 1990. What are plans for? Robot. Auton. Syst. 6, 1-2, 17--34.
2. Albore, A., Palacios, H., and Geffner, H. 2009. A translation-based approach to contingent planning. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 09). 1623--1628.
3. Bacchus, F. and Kabanza, F. 1996. Planning for temporally extended goals. In Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 2. 1215--1222.
4. Bagchi, S., Biswas, G., and Kawamura, K. 1996. Interactive task planning under uncertainty and goal changes. Robot. Auton. Syst. 18, 1, 157--167.
5. Baral, C., Kreinovich, V., and Trejo, R. 2001. Computational complexity of planning with temporal goals. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI'01). 509--514.
6. Benton, J., Do, M., and Kambhampati, S. 2009. Anytime heuristic search for partial satisfaction planning. Artif. Intell. 173, 5-6, 562--592.
7. Brick, T. and Scheutz, M. 2007. Incremental natural language processing for HRI. In Proceedings of the 2^ndACM IEEE International Conference on Human-Robot Interaction. 263--270.
8. Cantrell, R., Scheutz, M., Schermerhorn, P., and Wu, X. 2010. Robust spoken instruction understanding for HRI. In Proceedings of the Human-Robot Interaction Conference.
9. Cushing, W., Benton, J., and Kambhampati, S. 2008. Replanning as deliberative re-selection of objectives. Tech. rep., CSE Department, Arizona State University.
10. Do, M. and Kambhampati, S. 2002. Planning graph-based heuristics for cost-sensitive temporal planning. In Proceedings of the International Conference on Artificial Intelligence Planning Systems (AIPS'02). Vol. 2.
11. Dzifcak, J., Scheutz, M., Baral, C., and Schermerhorn, P. 2009. What to do and how to do it: Translating natural language directives into temporal and dynamic logic representation for goal management and action execution. In Proceedings of the International Conference on Robotics and Automation.
12. Etzioni, O., Golden, K., and Weld, D. S. 1997. Sound and efficient closed-world reasoning for planning. Artif. Intell. 89, 1-2, 113--148.
13. Ferguson, G., Allen, J., and Miller, B. 1996. TRAINS-95: Towards a mixed-initiative planning assistant. In Proceedings of the 3rd Conference on Artificial Intelligence Planning Systems (AIPS-96). 70--77.
14. Firby, R. 1989. Adaptive execution in complex dynamic worlds. Tech. rep., Yale University, New Haven, CT.
15. Gat, E. 1992. Integrating planning and reacting in a heterogeneous asynchronous architecture for controlling real-world mobile robots. In Proceedings of the National Conference on Artificial Intelligence. 809--809.
16. Gerevini, A., Haslum, P., Long, D., Saetti, A., and Dimopoulos, Y. 2009. Deterministic planning in the fifth international planning competition: Pddl3 and experimental evaluation of the planners. Artif. Intell. 173, 5-6, 619--668.
17. Golden, K. and Weld, D. S. 1996. Representing sensing actions: The middle ground revisited. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR'96). 174--185.
18. Hubbe, A., Ruml, W., Yoon, S., Benton, J., and Do, M. 2008. Online anticipatory planning. In Proceedings of the ICAPS'08 Workshop on a Reality Check for Planning and Scheduling under Uncertainty.
19. Kambhampati, S. 2007. Model-Lite planning for the Web age masses: The challenges of planning with incomplete and evolving domain theories. In Proceedings of the AAAI '07 Conference on Artificial Intelligence.
20. Knight, R., Rabideau, G., Chien, S., Engelhardt, B., and Sherwood, R. 2001. Casper: Space exploration through continuous planning. IEEE Intell. Syst., 70--75.
21. Lemai, S. and Ingrand, F. 2003. Interleaving temporal planning and execution: IxTeT-eXeC. In Proceedings of the ICAPS Workshop on Plan Execution.
22. Meuleau, N. and Smith, D. 2003. Optimal limited contingency planning. In Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence.
23. Myers, K. 1996. Advisable planning systems. Adv. Plan. Technol., 206--209.
24. Myers, K. 1998. Towards a framework for continuous planning and execution. In Proceedings of the AAAI Fall Symposium on Distributed Continual Planning.
25. Scherl, R. B. and Levesque, H. J. 1993. The frame problem and knowledge-producing actions. In Proceedings of the AAAI Conference on Artificial Intelligence. 689--695.
26. Schermerhorn, P., Benton, J., Scheutz, M., Talamadupula, K., and Kambhampati, S. 2009. Finding and exploiting goal opportunities in real-time during plan execution. In IEEE/RSJ International Conference on Intelligent Robots and Systems.
27. Scheutz, M. 2006. ADE - Steps towards a distributed development and runtime environment for complex robotic agent architectures. Appl. Artif. Intell. 20, 4-5, 275--304.
28. Scheutz, M., Schermerhorn, P., Kramer, J., and Anderson, D. 2007. First steps toward natural human-like HRI. Auton. Robot. 22, 4, 411--423.
29. Talamadupula, K., Benton, J., Schermerhorn, P., Scheutz, M., and Kambhampati, S. 2010. Integrating a closed-world planner with an open-world robot. In Proceedings of the AAAI Conference on Artificial Intelligence.
30. Yoon, S., Fern, A., and Givan, R. 2007. FF-Replan: A baseline for probabilistic planning. In Proceedings of the International Conference on Autonomous Planning and Scheduling (ICAPS'07). 352--359.
31. Yoon, S., Fern, A., Givan, R., and Kambhampati, S. 2008. Probabilistic planning via determinization in hindsight. In Proceedings of the AAAI Conference on Artificial Intelligence.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Planning and scheduling

  • Computer graphics

    • Graphics systems and interfaces

      • Perception