Communication constrained task allocation with optimized local task swaps | Autonomous Robots Skip to main content
Springer Nature Link
Log in

Communication constrained task allocation with optimized local task swaps

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

Communication constraints dictated by hardware often require a multi-robot system to make decisions and take actions locally. Unfortunately, local knowledge may impose limits that ultimately impede global optimality in a decentralized optimization problem. This paper enhances a recent anytime optimal assignment method based on a task-swap mechanism, redesigning the algorithm to address task allocation problems in a decentralized fashion. We propose a fully decentralized approach that allows local search processes to execute concurrently while minimizing interactions amongst the processes, needing neither global broadcast nor a multi-hop communication protocol. The formulation is analyzed in a novel way using tools from group theory and optimization duality theory to show that the convergence of local searching processes is related to a shortest path routing problem on a graph subject to the network topology. Simulation results show that this fully decentralized method converges quickly while sacrificing little optimality.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The main algorithm was first presented at the 2014 Robotics: Science and Systems conference (Liu et al. 2014).

  2. Note that this notation represents a change from our conference paper (Liu et al. 2014). The arrow direction in the present work better illustrates the underlying task-exchange operator.

  3. The symbols u and v will be used as vertices of graphs in the remainder of the paper. They are not to be confused with their use earlier as dual variables.

References

  • Balinski, M. L., & Gomory, R. E. (1964). A primal method for the assignment and transportation problems. Management Science, 10(3), 578–593.

    Article  Google Scholar 

  • Bertsekas, D. P. (1979). A distributed algorithm for the assignment problem. Lab. for Information and Decision Systems Report, MIT.

  • Burkard, R. E., Dell’Amico, M., & Martello, S. (2009). Assignment problems. New York: Society for Industrial and Applied Mathematics.

    Book  MATH  Google Scholar 

  • Chaimowicz, L., Campos, M. F. M., & Kumar, V. (2002). Dynamic role assignment for cooperative robots. In Proc. of the IEEE Intl. Conf. on Robotics and Automation (pp. 293–298).

  • Chechetka, A., & Sycara, K. (2006). No-commitment branch and bound search for distributed constraint optimization. In Proceedings of Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems (pp. 1427–1429).

  • Derigs, U. (1985). The shortest augmenting path method for solving assignment problems—motivation and computational experience. Annals of Operations Research, 4, 57–102.

    Article  MathSciNet  Google Scholar 

  • Dias, M. B., Zlot, R., Kalra, N., & Stentz, A. (2006). Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE, 94(7), 1257–1270.

    Article  Google Scholar 

  • Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2), 248–264.

    Article  MATH  Google Scholar 

  • Farinelli, A., Iocchi, L., Nardi, D., & Ziparo, V. A. (2006). Assignment of dynamically perceived tasks by token passing in multi-robot systems. In Proc. of the IEEE, Special Issue on Multi-robot Systems.

  • George, D. (1963). Linear Programming and Extensions. Princeton: Princeton University Press.

    Google Scholar 

  • Gerkey, B. P., & Matarić, M. J. (2002). Sold!: Auction methods for multirobot coordination. EEE Transactions on Robotics and Automation, 18(5), 758–768.

    Article  Google Scholar 

  • Gerkey, B. P., & Matarić, M. J. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems. International Journal of Robotics Research, 23(9), 939–954.

    Article  Google Scholar 

  • Giordani, S., Lujak, M., & Martinelli, F. (2010). A distributed algorithm for the multi-robot task allocation problem. LNCS: Trends in Applied Intelligent Systems, 6096, 721–730.

    Google Scholar 

  • Goldberg, A. V., & Kennedy, R. (1995). An efficient cost scaling algorithm for the assignment problem. Mathematical Programming, 71(2), 153–177.

    Article  MATH  MathSciNet  Google Scholar 

  • Golfarelli, M., Maio, D., & Rizzi, S. (1997). Multi-agent path planning based on task-swap negotiation. In Proc. UK Planning and Scheduling Special Interest Group Workshop (pp. 69–82).

  • Hirayama, K., & Yokoo, M. (1997). Distributed partial constraint satisfaction problem. In Principles and Practice of Constraint Programming (pp. 222–236).

  • Korsah, G. A., Stentz, A., & Dias, M. B. (2013). A comprehensive taxonomy for multi-robot task allocation. International Journal of Robotics Research, 32(12), 1495–1512.

    Article  Google Scholar 

  • Kuhn, H. W. (1955). The Hungarian method for the assignment poroblem. Naval Research Logistic Quarterly, 2, 83–97.

    Article  Google Scholar 

  • Lagoudakis, M. G., Markakis, E., Kempe, D., Keskinocak, P., Kleywegt, A., Koenig, S., et al. (2005). Auction-based multi-robot routing. In Robotics: Science and Systems.

  • Lemaire, T., Alami, R., & Lacroix, S. (2004). A distributed tasks allocation scheme in multi-UAV context. In Proc. ICRA (pp. 3622–3627).

  • Liu, L., & Shell, D. A. (2012a). Multi-robot formation morphing through matching graph. In International Symposium on Distributed Autonomous Robotic Systems (DARS).

  • Liu, L., & Shell, D. A. (2012b). A distributable and computation-flexible assignment algorithm: From local task swapping to global optimality. In Proceedings of Robotics: Science and Systems.

  • Liu, L., & Shell, D. A. (2013). An anytime assignment algorithm: From local task swapping to global optimality. Autonomous Robots, 35, 271–286.

    Article  Google Scholar 

  • Liu, L., Michael, N., & Shell, D. (2014). Fully decentralized task swaps with optimized local searching. In Proceedings of Robotics: Science and Systems, Berkeley, USA, July 2014.

  • Michael, N., Zavlanos, M.M., Kumar, V., & Pappas, G.J. (2008). Distributed multi-robot task assignment and formation control. In IEEE Intl. Conf on Robotics and Automation (pp. 128–133).

  • Modi, P. J., Shen, W.-M., Tambe, M., & Yokoo, M. (2006). Adopt: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence, 161, 149–180.

    Article  MathSciNet  Google Scholar 

  • Parker, L. E. (2008). Multiple mobile robot systems. In Bruno Siciliano & Oussama Khatib (Eds.), Handbook of robotics, chapter 40. New York: Springer.

    Google Scholar 

  • Pentico, D. W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176, 774–793.

    Article  MATH  MathSciNet  Google Scholar 

  • Petcu, A., & Faltings, B. (2005). A scalable method for multiagent constraint optimization. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI’05 (pp. 266–271).

  • Rotman, J. J. (1995). An introduction to the theory of groups (Vol. 148). New York: Springer Science & Business Media.

    MATH  Google Scholar 

  • Sariel, S., & Balch, T. (2006). A distributed multi-robot cooperation framework for real time task achievement. In Proceedings of Distributed Autonomous Robotic Systems

  • Stone, P., Kaminka, G. A., Kraus, S., & Rosenschein, J. S. (2010). Ad Hoc Autonomous Agent Teams: collaboration without pre-coordination. In Proc. AAAI

  • Sung, C., Ayanian, N., & Rus, D. (2013). Improving the performance of multi-robot systems by task switching. In IEEE International Conference on Robotics and Automation (pp. 2984–2991).

  • Tang, F., & Parker, L.E. (2007). A complete methodology for generating multi-robot task solutions using ASyMTRe-D and market-based task allocation. In Proc. of IEEE International Conference on Robotics and Automation (ICRA’93) (pp. 3351–3358).

  • Turpin, M., Mohta, K., Michael, N., & Kumar, V. (2013). Goal assignment and trajectory planning for large teams of aerial robots. In Proceedings of Robotics: Science and Systems, Berlin, Germany, June 2013.

  • Turpin, M., Michael, N., & Kumar, V. (2014). CAPT: Concurrent assignment and planning of trajectories for multiple robots. International Journal of Robotics Research, 33(1), 98–112.

    Article  Google Scholar 

  • Wawerla, J., & Vaughan, R. T. (2009). Robot task switching under diminishing returns. In Proceedings of the 2009 IEEE/RSJ international conference on Intelligent robots and systems, IROS’09 (pp. 5033–5038).

  • Yeoh, W., Felner, A., & Koenig, S. (2008). Bnb-adopt: An asynchronous branch-and-bound dcop algorithm. In In Proceedings of AAMAS (pp. 591–598).

  • Zavlanos, M.M., Spesivtsev, L., & Pappas, G. J. (2008). A distributed auction algorithm for the assignment problem. In Proceedings of the IEEE Conference on Decision and Control (pp. 1212–1217), Cancun, Mexico, December 2008.

  • Zheng, X., & Koenig, S. (2009). K-swaps: Cooperative negotiation for solving task-allocation problems. In Proc. IJCAI (pp. 373–378).

  • Zlot, R., & Stentz, A. (2006). Market-based multirobot coordination for complex tasks. The International Journal of Robotic Research, 25(1), 73–101.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Robotics Institute, Carnegie Mellon University, Pittsburgh, USA

    Lantao Liu & Nathan Michael

  2. Department of Computer Science and Engineering, Texas A&M University, College Station, USA

    Dylan A. Shell

Authors
  1. Lantao Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nathan Michael
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dylan A. Shell
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lantao Liu.

Additional information

This is one of several papers published in Autonomous Robots comprising the “Special Issue on Robotics Science and Systems”.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, L., Michael, N. & Shell, D.A. Communication constrained task allocation with optimized local task swaps. Auton Robot 39, 429–444 (2015). https://doi.org/10.1007/s10514-015-9481-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-015-9481-9

Keywords

Search

Navigation