Hostname: page-component-76fb5796d-x4r87 Total loading time: 0 Render date: 2024-04-26T22:06:25.229Z Has data issue: false hasContentIssue false
  • English
  • Français

Finding optimal plans for multiple teams of robots through a mediator: A logic-based approach

Published online by Cambridge University Press:  25 September 2013

ESRA ERDEM ,
VOLKAN PATOGLU ,
ZEYNEP G. SARIBATUR ,
PETER SCHÜLLER  and
TANSEL URAS
ESRA ERDEM
Affiliation:
Faculty of Engineering and Natural Sciences, Sabancı University, İstanbul, Turkey
VOLKAN PATOGLU
Affiliation:
Faculty of Engineering and Natural Sciences, Sabancı University, İstanbul, Turkey
ZEYNEP G. SARIBATUR
Affiliation:
Faculty of Engineering and Natural Sciences, Sabancı University, İstanbul, Turkey
PETER SCHÜLLER
Affiliation:
Faculty of Engineering and Natural Sciences, Sabancı University, İstanbul, Turkey
TANSEL URAS
Affiliation:
Department of Computer Science, University of Southern California, Los Angeles, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the problem of finding optimal plans for multiple teams of robots through a mediator, where each team is given a task to complete in its workspace on its own and where teams are allowed to transfer robots between each other, subject to the following constraints: 1) teams (and the mediator) do not know about each other's workspace or tasks (e.g., for privacy purposes); 2) every team can lend or borrow robots, but not both (e.g., transportation/calibration of robots between/for different workspaces is usually costly). We present a mathematical definition of this problem and analyze its computational complexity. We introduce a novel, logic-based method to solve this problem, utilizing action languages and answer set programming for representation, and the state-of-the-art ASP solvers for reasoning. We show the applicability and usefulness of our approach by experiments on various scenarios of responsive and energy-efficient cognitive factories.

Keywords

answer set programmingdecoupled planningcognitive robotics
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 13 , Issue 4-5: 29th International Conference on Logic Programming , July 2013 , pp. 831 - 846
Copyright
Copyright © 2013 [ESRA ERDEM, VOLKAN PATOGLU, ZEYNEP G. SARIBATUR, PETER SCHÜLLER and TANSEL URAS] 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aker, E., Patoglu, V. and Erdem, E. 2012. Answer set programming for reasoning with semantic knowledge in collaborative housekeeping robotics. In Proc. of IFAC SYROCO.CrossRefGoogle Scholar
Alami, R., Ingrand, F. and Qutub, S. 1998. A scheme for coordinating multi-robots planning activities and plans execution. In Proc. of ECAI, 617–621.Google Scholar
Beetz, M., Buss, M. and Wollherr, D. 2007. CTS - What is the role of artificial intelligence? In Proc. of KI, 19–42.Google Scholar
Brewka, G., Eiter, T. and Truszczynski, M. 2011. Answer set programming at a glance. Communications of the ACM 54, 12, 92–103.Google Scholar
Casolary, M. and Lee, J. 2011. Representing the language of the causal calculator in answer set programming. In Proc. of ICLP (Technical Communications), 51–61.Google Scholar
Chevaleyre, Y., Dunne, P. E., Endriss, U., Lang, J., Lemaître, M., Maudet, N., Padget, J. A., Phelps, S., Rodríguez-Aguilar, J. A. and Sousa, P. 2006. Issues in multiagent resource allocation. Informatica 30, 1, 3–31.Google Scholar
Dantsin, E., Eiter, T., Gottlob, G. and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Computing Surveys 33, 3, 374–425.Google Scholar
Decker, K. and Lesser, V. 1994. Designing a family of coordination algorithms. In Proc. of DAI, 65–84.Google Scholar
Dovier, A., Formisano, A. and Pontelli, E. 2013. Autonomous agents coordination: Action languages meet clp() and linda. TPLP 13, 2, 149–173.Google Scholar
Durfee, E. H. and Lesser, V. R. 1987. Planning coordinated actions in dynamic domains. In Proc. of the DARPA Knowledge-Based Planning Workshop, 18.1–18.10.Google Scholar
Ehtamo, H., Hamalainen, R. P., Heiskanen, P., Teich, J., Verkama, M. and Zionts, S. 1999. Generating pareto solutions in a two-party setting: Constraint proposal methods. Management Science 45, 12, 1697–1709.CrossRefGoogle Scholar
Ephrati, E. and Rosenschein, J. S. 1993. Multi-agent planning as the process of merging distributed sub-plans. In Proc. of DAI, 115–129.Google Scholar
Erdem, E., Aker, E. and Patoglu, V. 2012. Answer set programming for collaborative housekeeping robotics: Representation, reasoning, and execution. Intelligent Service Robotics 5, 4, 275–291.Google Scholar
Erdem, E., Haspalamutgil, K., Palaz, C., Patoglu, V. and Uras, T. 2011. Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation. In Proc. of ICRA.Google Scholar
Erdem, E., Haspalamutgil, K., Patoglu, V. and Uras, T. 2012. Causality-based planning and diagnostic reasoning for cognitive factories. In Proc. of IEEE International Conference on Emerging Technologies and Factory Automation (ETFA).Google Scholar
Erdem, E. and Patoglu, V. 2012. Applications of action languages in cognitive robotics. In Correct Reasoning 229–246.Google Scholar
Erol, K., Nau, D. S. and Subrahmanian, V. S. 1995. Complexity, decidability and undecidability results for domain-independent planning. Artificial Intelligence 76, 1–2, 75–88.Google Scholar
Foulser, D., Li, M. and Yang, Q. 1992. Theory and algorithms for plan merging. Artificial Intelligence Journal 57, 143–182.CrossRefGoogle Scholar
Gaston, M. E. and desJardins, M. 2008. The effect of network structure on dynamic team formation in multi-agent systems. Computational Intelligence 24, 2, 122–157.CrossRefGoogle Scholar
Gebser, M., Kaminski, R., König, A. and Schaub, T. 2011. Advances in gringo series 3. In Proc. of LPNMR, 345–351.Google Scholar
Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T. 2007. clasp: A conflict-driven answer set solver. In Proc. of LPNMR, 260–265.Google Scholar
Gelfond, M. and Lifschitz, V. 1998. Action languages. Electronic Transactions on Artificial Intelligence 2, 193–210.Google Scholar
Georgeff, M. P. 1988. Communication and interaction in multi-agent planning. In Readings in Distributed AI, 200–204.Google Scholar
Giunchiglia, E., Lee, J., Lifschitz, V., McCain, N. and Turner, H. 2004. Nonmonotonic causal theories. AIJ 153, 49–104.Google Scholar
Hamadi, Y., Jabbour, S. and Sais, L. 2009. Control-based clause sharing in parallel sat solving. In Proc. of IJCAI, 499–504.Google Scholar
Havur, G., Haspalamutgil, K., Palaz, C., Erdem, E. and Patoglu, V. 2013. A case study on the tower of hanoi challenge: Representation, reasoning and execution. In Proc. of ICRA.CrossRefGoogle Scholar
Hunsberger, L. and Grosz, B. J. 2000. A combinatorial auction for collaborative planning. In Proc. of ICMAS, 151–158.Google Scholar
Kowalski, R. A. and Sadri, F. 2013. Towards a logic-based unifying framework for computing. CoRR abs/1301.6905.Google Scholar
Lifschitz, V. 2002. Answer set programming and plan generation. Artificial Intelligence 138, 39–54.Google Scholar
Lifschitz, V. 2008. What is answer set programming. In Proc. of AAAI, MIT Press, 1594–1597.Google Scholar
Lin, S.-H. 2011. Coordinating time-constrained multi-agent resource sharing with fault detection. In Proc. of IEEM, 1000–1004.Google Scholar
de Weerdt, M. M., B. J. C. 2009. Introduction to planning in multiagent systems. Multiagent and Grid Systems 5, 345–355.CrossRefGoogle Scholar
Marek, V. and Truszczyński, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-Year Perspective, Springer Verlag, 375–398.Google Scholar
McCain, N. and Turner, H. 1997. Causal theories of action and change. In Proc. of AAAI/IAAI, 460–465.Google Scholar
Nair, R., Tambe, M. and Marsella, S. 2002. Team formation for reformation in multiagent domains like robocuprescue. In Proc. of RoboCup, 150–161.Google Scholar
Niemelä, I. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 241–273.Google Scholar
Shoham, Y. and Tennenholtz, M. 1995. On social laws for artificial agent societies:off-line design. Artificial Intelligence 73, 231–252.Google Scholar
Stuart, C. 1985. An implementation of a multi-agent plan synchronizer. In Proc. of IJCAI, 1031–1033.Google Scholar
Sycara, K. P., Roth, S. P., Sadeh, N. M. and Fox, M. S. 1991. Resource allocation in distributed factory scheduling. IEEE Expert 6, 1, 29–40.Google Scholar
ter Mors, A., Valk, J. and Witteveen, C. 2004. Coordinating autonomous planners. In Proc. of IC-AI, 795–801.Google Scholar
Trejo, R., Galloway, J., Sachar, C., Kreinovich, V., Baral, C. and Tuan, L.-C. 2001. From planning to searching for the shortest plan: An optimal transition. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 9, 6, 827–837.CrossRefGoogle Scholar
Turner, H. 2002. Polynomial-length planning spans the polynomial hierarchy. In Proc. of JELIA, 111–124.Google Scholar
van der Krogt, R., Roos, N., de Weerdt, M. and Witteveen, C. 2005. Multiagent planning through plan repair. In Proc. of AAMAS, 1337–1338.Google Scholar
Yang, Q., Nau, D. S. and Hendler, J. 1992. Merging separately generated plans with restricted interactions. Computational Intelligence 8, 648–676.Google Scholar
Zaeh, M., Beetz, M., Shea, K., Reinhart, G., Bender, K., Lau, C., Ostgathe, M., Vogl, W., Wiesbeck, M., Engelhard, M., Ertelt, C., Rhr, T., Friedrich, M. and Herle, S. 2009. The cognitive factory. In Changeable and Reconfigurable Manufacturing Systems, 355–371.Google Scholar
Zaeh, M., Ostgathe, M., Geiger, F. and Reinhart, G. 2012. Adaptive job control in the cognitive factory. In Enabling Manufacturing Competitiveness and Economic Sustainability, ElMaraghy, H. A., Ed. Springer, Berlin Heidelberg, 10–17.Google Scholar
Supplementary material: PDF

Erdem et al. supplementary material

Appendix

Download Erdem et al. supplementary material(PDF)
PDF 343.5 KB