IP Library › Granted Patent US 12,282,314
Granted Patent B2
US 12,282,314 · App. 17/587,532 · Granted Apr 22, 2025

Hypergraph search for real-time multi-robot task allocation in a smart factory

Inventors: Zixiang Nie (Tampa, FL); Kwang-Cheng Chen (Tampa, FL)
Assignee: University of South Florida
G05B19/41865G05B19/41895G06N5/01
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,282,314
App. No.
17/587,532
Granted
Apr 22, 2025
Kind
B2
Abstract

Task assignment for multi-robot systems (MRSs) in a smart factory (Industry 4.0) is described. Aspects are directed to a hypergraph based MRS and production model facilitating the cooperation among robots and serving frequent reconfiguration desired in Industry 4.0. Aspects are directed to a time complexity friendly search algorithm for real-time application using a hypergraph model to get task assignment(s). Parameters are provided for a tradeoff between solution optimality and time complexity. In an implementation, an example system can include a MRS including robots, wherein the MRS is configured to perform a manufacturing task, and a computing device configure to perform a multi-robot task allocation (MRTA) for the MRS. In an implementation, an example method can include generating task assignments, using MRTA, for robots of a MRS including the robots, wherein the MRS is configured to perform a manufacturing task, and providing the task assignments to the MRS.

Claims (27)

1. A system comprising:

a multi-robot system (MRS) comprising a plurality of robots, wherein the MRS is configured to perform a manufacturing task, wherein the plurality of robots comprises a plurality of production robots and a plurality of autonomous mobile robots (AMRs);

a computing device in electronic communication with the MRS configured to:

perform a multi-robot task allocation (MRTA) for the MRS, wherein the MRTA is configured to generate task assignments for each of the plurality of production robots and transportation paths for each of the plurality of AMRs,

adjust the task assignments and transportation paths to assign flows in real-time through iterative execution of a hypergraph search algorithm that is optimized for energy efficiency within the MRS and based at least in part on a hypergraph production robot model corresponding with the MRS, wherein each hyper-vertex of the hypergraph production robot model represents a respective AMR, wherein each directed edge set of the hypergraph production robot model represents a transportation path set with corresponding quantized energy consumption as weights, and wherein the hypergraph search algorithm is configured to: (a) perform biased sampling in favor of higher energy efficiency solutions from an entire solution space, and (b) stop the iterative execution based on marginal distribution bounds estimations determined based on the weights.

2. The system of claim 1 , wherein the MRTA is performed in real-time.

3. The system of claim 1 , wherein the MRTA is configured to generate real-time decisions regarding tasks for the robots.

4. The system of claim 1 , wherein each robot is configured to be involved in a manufacture of multiple products.

5. The system of claim 1 , wherein a hypergraph search algorithm is configured to use the hypergraph production robot model to generate the task assignments and the transportation paths.

6. The system of claim 5 , wherein the task assignments are optimized to MRS productivity.

7. The system of claim 5 , wherein the transportation paths are optimized to control energy consumption.

8. The system of claim 1 , wherein the computing device is configured to assign flows in real-time by:

receiving manufacturing demands for the plurality of robots,

generating a product plan sequence for each of a plurality of products in distinct orders,

determining at least one product plan sequence constraint and at least one hypergraph production robot model constraint,

generating a flow for each product using the at least one product plan sequence constraint and the at least one hypergraph production robot model constraint, and

assigning each flow to a respective robot of the plurality of robots as a task.

9. The system of claim 1 , wherein the hypergraph search algorithm comprises at least one of a constant time algorithm or a nested hierarchy hypergraph search algorithm.

10. A method comprising:

generating task assignments, using multi-robot task allocation (MRTA), for a plurality of robots of a multi-robot system (MRS) comprising the plurality of robots, wherein the MRS is configured to perform a manufacturing task, wherein the plurality of robots comprises a plurality of production robots and a plurality of autonomous mobile robots (AMRs), wherein the MRTA is configured to:

generate task assignments for the production robots and transportation paths for the AMRs,

adjust the task assignments and transportation paths to assign production flows in real-time through iterative execution of a hypergraph search algorithm that is optimized for energy efficiency within the MRS and based at least in part on a hypergraph production robot model corresponding with the MRS, wherein each hyper-vertex of the hypergraph production robot model represents a respective AMR, and each directed edge set of the hypergraph production robot model represents a transportation path set with corresponding quantized energy consumption as weights, and wherein the hypergraph search algorithm is configured to: (a) perform biased sampling in favor of higher energy efficiency solutions from an entire solution space, and (b) stop the iterative execution based on marginal distribution bounds estimations determined based on the weights.

11. The method of claim 10 , further comprising reconfiguring the MRS using the task assignments.

12. The method of claim 10 , wherein the MRTA is configured to generate real-time decisions regarding tasks for the robots.

13. The method of claim 10 , wherein each robot is configured to be involved in a manufacture of multiple products.

14. The method of claim 10 , further comprising adjusting the task assignments and the transportation paths in real-time.

15. The method of claim 10 , wherein the task assignments are optimized to MRS productivity.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 28, 2022
From: NIE, ZIXIANG; CHEN, KWANG-CHENG
To: UNIVERSITY OF SOUTH FLORIDA
Reel/Frame 059766/0988 →
Continuity (2)
Provisional Application 63143978 · Feb 1, 2021
Related Publication 20220253048A1 · Aug 11, 2022
References Cited (70)
US 9008839B1 · Kuffner et al. · 2015 [cited by applicant]
US 10331644B2 · Smart · 2019 [cited by examiner]
US 10525591B1 · Baroudi et al. · 2020 [cited by applicant]
US 11119496B1 · Ebrahimi Afrouzi · 2021 [cited by examiner]
US 20100223087A1 · Durr · 2010 [cited by examiner]
US 20100241248A1 · Zhang · 2010 [cited by examiner]
US 20210326652A1 · Hazard · 2021 [cited by examiner]
US 20220179882A1 · Cervantes · 2022 [cited by examiner]
US 20220197259A1 · Poisson · 2022 [cited by examiner]
CN 101945492A · 2011 [cited by applicant]
CN 105069530B · 2019 [cited by applicant]
CN 111258316A · 2020 [cited by examiner]
Bampas, E., Das, S., Dereniowski, D. and Karousatou, C.. Collaborative delivery by energy-sharing low-power mobile robots. In Algorithms for Sensor Systems: 13th International Symposium on Algorithms and Experiments for… [cited by examiner]
Wong, A.K., 1987. Knowledge representation for robot vision and path planning using attributed graphs and hypergraphs. In Machine Intelligence and Knowledge Engineering for Robotic Applications (pp. 113-143). (Year: 198… [cited by examiner]
Liu, L. and Shell, D.A., 2012. Large-scale multi-robot task allocation via dynamic partitioning and distribution. Autonomous Robots, 33, pp. 291-307. (Year: 2012). [cited by examiner]
Ozdal, M.M. and Aykanat, C., 2004. Hypergraph models and algorithms for data-pattern-based clustering. Data Mining and Knowledge Discovery, 9, pp. 29-57. (Year: 2004). [cited by examiner]
Wong, A.K., 1987. Knowledge representation for robot vision and path planning using attributed graphs and hypergraphs. In Machine Intelligence and Knowledge Engineering for Robotic Applications (pp. 113-143). Berlin, He… [cited by examiner]
Magri, L. and Fusiello, A., 2017. Multiple structure recovery via robust preference analysis. Image and Vision Computing, 67, pp. 1-15. (Year: 2017). [cited by examiner]
Fayek, R.E. and Wong, A.K., Apr. 1996, Using hypergraph knowledge representation for natural terrain robot navigation and path planning. In Proceedings of IEEE International Conference on Robotics and Automation (vol. 4… [cited by examiner]
Zaidi, L., Sahnoun, M.H. and Bettayeb, B., 2019. Task allocation based on shared resource constraint for multi-robot systems in manufacturing industry. IFAC-PapersOnLine, 52(13), pp. 2020-2025. (Year: 2019). [cited by examiner]
Huang, Yin, Yi Zhang, and Hong Xiao. “Multi-robot system task allocation mechanism for smart factory.” 2019 IEEE 8th Joint International Information Technology and Artificial Intelligence Conference (ITAIC). IEEE, 2019.… [cited by applicant]
Sung, Cynthia, Nora Ayanian, and Daniela Rus. “Improving the performance of multi-robot systems by task switching.” 2013 IEEE International Conference on Robotics and Automation. IEEE, 2013. [cited by applicant]
S. Wang, J. Wan, D. Li, and C. Zhang, “Implementing smart factory of industrie 4.0: an outlook,” International journal of distributed sensor networks, vol. 12, No. 1, p. 3159805, 2016. [cited by applicant]
H. Lasi, P. Fettke, H.-G. Kemper, T. Feld, and M. Hoffmann, “Industry 4.0,” Business & information systems engineering, vol. 6, No. 4, pp. 239-242, 2014. [cited by applicant]
J. R. Duflou, J. W. Sutherland, D. Dornfeld, C. Herrmann, J. Jeswiet, S. Kara, M. Hauschild, and K. Kellens, “Towards energy and resource efficient manufacturing: A processes and systems approach,” CIRP annals, vol. 61,… [cited by applicant]
J. Wan, B. Chen, S. Wang, M. Xia, D. Li, and C. Liu, “Fog computing for energy-aware load balancing and scheduling in smart factory,” IEEE Transactions on Industrial Informatics, vol. 14, No. 10, pp. 4548-4556, 2018. [cited by applicant]
T. Stock and G. Seliger, “Opportunities of sustainable manufacturing in industry 4.0,” Procedia Cirp, vol. 40, pp. 536-541, 2016. [cited by applicant]
M. Ghobakhloo, “Industry 4.0, digitization, and opportunities for sustainability,” Journal of Cleaner Production, vol. 252, p. 119869, 2020. [cited by applicant]
K.-D. Thoben, S. Wiesner, and T. Wuest, “industrie 4.0 and smart manufacturing—a review of research issues and application examples,” International journal of automation technology, vol. 11, No. 1, pp. 4-16, 2017. [cited by applicant]
S. Wang, J. Wan, D. Zhang, D. Li, and C. Zhang, “Towards smart factory for industry 4.0: a self-organized multi-agent system with big data based feedback and coordination,” Computer Networks, vol. 101, pp. 158-168, 2016. [cited by applicant]
Z. Jakovljevic, V. Lesi, S. Mitrovic, and M. Pajic, “Distributing sequential control for manufacturing automation systems,” IEEE Transactions on Control Systems Technology, 2019. [cited by applicant]
K.-C. Chen, S.-C. Lin, J.-H. Hsiao, C.-H. Liu, A. F. Molisch, and G. P. Fettweis, “Wireless networked multirobot systems in smart factories,” Proceedings of the IEEE, vol. 109, No. 4, pp. 468-494, 2021. [cited by applicant]
G. Fortino, F. Messina, D. Rosaci, G. M. L. Sarn'e, and C. Savaglio, “A trust-based team formation framework for mobile intelligence in smart factories,” IEEE Transactions on Industrial Informatics, vol. 16, No. 9, pp. … [cited by applicant]
Y. Rizk, M. Awad, and E. W. Tunstel, “Cooperative heterogeneous multirobot systems: a survey,” ACM Computing Surveys (CSUR), vol. 52, No. 2, pp. 1-31, 2019. [cited by applicant]
D. Herrero-Perez and H. Martinez-Barbera, “Modeling distributed transportation systems composed of flexible automated guided vehicles in flexible manufacturing systems,” IEEE Transactions on Industrial Informatics, vol.… [cited by applicant]
K.-C. Chen, Y. Wang, Z. Nie, and Q. Cui, “Toward holistic integration of computing and wireless networking,” in IFIP International Internet of Things Conference. Springer, 2019, pp. 219-234. [cited by applicant]
J.-H. Hsiao and K.-C. Chen, “Network analysis of collaborative cyberphysical multi-agent smart manufacturing systems,” in 2019 IEEE/CIC International Conference on Communications in China (ICCC). IEEE, 2019, pp. 219-224. [cited by applicant]
P. Lade, R. Ghosh, and S. Srinivasan, “Manufacturing analytics and industrial internet of things,” IEEE Intelligent Systems, vol. 32, No. 3, pp. 74-79, 2017. [cited by applicant]
J. Wan, B. Chen, M. Imran, F. Tao, D. Li, C. Liu, and S. Ahmad, “Toward dynamic resources management for iot-based manufacturing,” IEEE Communications Magazine, vol. 56, No. 2, pp. 52-59, 2018. [cited by applicant]
J. Wan, X. Li, H. N. Dai, A. Kusiak, M. Mart'nez-Garc'ia, and D. Li, “Artificial-intelligence-driven customized manufacturing factory: Key technologies, applications, and challenges,” Proceedings of the IEEE, vol. 109, … [cited by applicant]
Y. Liu and X. Xu, “Industry 4.0 and cloud manufacturing: A comparative analysis,” Journal of Manufacturing Science and Engineering, vol. 139, No. 3, 2017. [cited by applicant]
K. E. Booth, G. Nejat, and J. C. Beck, “A constraint programming approach to multi-robot task allocation and scheduling in retirement homes,” in International conference on principles and practice of constraint programm… [cited by applicant]
A. Dutta, E. Czarnecki, V. Ufimtsev, and A. Asaithambi, “Correlation clustering- based multi-robot task allocation: a tale of two graphs,” ACM SIGAPP Applied Computing Review, vol. 19, No. 4, pp. 5-16, 2020. [cited by applicant]
M. Afrin, J. Jin, A. Rahman, Y.-C. Tian, and A. Kulkarni, “Multiobjective resource allocation for edge cloud based robotic workflow in smart factory,” Future Generation Computer Systems, vol. 97, pp. 119-130, 2019. [cited by applicant]
I. Suemitsu, K. Izui, T. Yamada, S. Nishiwaki, A. Noda, and T. Nagatani, “Simultaneous optimization of layout and task schedule for robotic cellular manufacturing systems,” Computers & Industrial Engineering, vol. 102, … [cited by applicant]
Y. Koren, W. Wang, and X. Gu, “Value creation through design for scalability of reconfigurable manufacturing systems,” International Journal of Production Research, vol. 55, No. 5, pp. 1227-1242, 2017. [cited by applicant]
J. Chen and D. Sun, “Coalition-based approach to task allocation of multiple robots with resource constraints,” IEEE Transactions on Automation Science and Engineering, vol. 9, No. 3, pp. 516-528, 2012. [cited by applicant]
C. Henkel, J. Abbenseth, and M. Toussaint, “An optimal algorithm to solve the combined task allocation and path finding problem,” arXiv preprint arXiv:1907.10360, 2019. [cited by applicant]
J. Zhou, X. Zhao, X. Zhang, D. Zhao, and H. Li, “Task allocation for multi-agent systems based on distributed many-objective evolutionary algorithm and greedy algorithm,” IEEE Access, vol. 8, pp. 19 306-19 318, 2020. [cited by applicant]
L. Liu and D. A. Shell, “Large-scale multi-robot task allocation via dynamic partitioning and distribution,” Autonomous Robots, vol. 33, No. 3, pp. 291-307, 2012. [cited by applicant]
W. Wang and Y. Jiang, “Community-aware task allocation for social networked multiagent systems,” IEEE transactions on cybernetics, vol. 44, No. 9, pp. 1529-1543, 2013. [cited by applicant]
M. Otte, M. J. Kuhlman, and D. Sofge, “Auctions for multi-robot task allocation in communication limited environments,” Autonomous Robots, vol. 44, No. 3, pp. 547-584, 2020. [cited by applicant]
F. Zitouni, S. Harous, and R. Maamri, “A distributed approach to the multi-robot task allocation problem using the consensus-based bundle algorithm and ant colony system,” IEEE Access, vol. 8, pp. 27 479-27 494, 2020. [cited by applicant]
A. Liu, M. Pfund, and J. Fowler, “Scheduling optimization of task allocation in integrated manufacturing system based on task decomposition,” Journal of Systems Engineering and Electronics, vol. 27, No. 2, pp. 422-433, … [cited by applicant]
B. P. Gerkey and M. J. Mataric, “A formal analysis and taxonomy of task allocation in multi-robot systems,” The International journal of robotics research, vol. 23, No. 9, pp. 939-954, 2004. [cited by applicant]
Y. Fang, C. Peng, P. Lou, Z. Zhou, J. Hu, and J. Yan, “Digital-twin-based job shop scheduling toward smart manufacturing,” IEEE Transactions on Industrial Informatics, vol. 15, No. 12, pp. 6425-6435, 2019. [cited by applicant]
D. Baumann, F. Mager, U. Wetzker, L. Thiele, M. Zimmerling, and S. Trimpe, “Wireless control for smart manufacturing: Recent approaches and open challenges,” Proceedings of the IEEE, vol. 109, No. 4, pp. 441-467, 2021. [cited by applicant]
Z. Zhuang, Z. Huang, Y. Sun, and W. Qin, “Optimization for cooperative task planning of heterogeneous multi-robot systems in an order picking warehouse,” Engineering Optimization, pp. 1-18, 2020. [cited by applicant]
G. A. Korsah, A. Stentz, and M. B. Dias, “A comprehensive taxonomy for multi-robot task allocation,” The International Journal of Robotics Research, vol. 32, No. 12, pp. 1495-1512, 2013. [cited by applicant]
V. Tereshchuk, J. Stewart, N. Bykov, S. Pedigo, S. Devasia, and A. G. Banerjee, “An efficient scheduling algorithm for multi-robot task allocation in assembling aircraft structures,” IEEE Robotics and Automation Letters… [cited by applicant]
H. Touzani, H. Hadj-Abdelkader, N. S'eguy, and S. Bouchafa, “Multirobot task sequencing automatic path planning for cycle time optimization: Application for car production line,” IEEE Robotics and Automation Letters, vo… [cited by applicant]
A. Maoudj, B. Bouzouia, A. Hentout, A. Kouider, and R. Toumi, “Distributed multi-agent scheduling and control system for robotic flexible assembly cells,” Journal of Intelligent Manufacturing, vol. 30, No. 4, pp. 1629-1… [cited by applicant]
K. Chen, T. Zhang, R. D. Gitlin, and G. Fettweis, “Ultra-low latency mobile networking,” IEEE Network, vol. 33, No. 2, pp. 181-187, 2019. [cited by applicant]
J. Wang, Y. Zhang, Y. Liu, and N. Wu, “Multiagent and bargaininggame-based real-time scheduling for internet of things-enabled flexible job shop,” IEEE Internet of Things Journal, vol. 6, No. 2, pp. 2518-2531, 2019. [cited by applicant]
S. Choudhury, J. Gupta, M. Kochenderfer, D. Sadigh, and J. Bohg, “Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints,” in Proceedings of Robotics: Science and Systems, Corvalis, Oregon, USA, … [cited by applicant]
Z. Jiang, Y. Jin, M. E, and Q. Li, “Distributed dynamic scheduling for cyber-physical production systems based on a multi-agent system,” IEEE Access, vol. 6, pp. 1855-1869, 2018. [cited by applicant]
X. Li, D. Li, J. Wan, A. V. Vasilakos, C.-F. Lai, and S. Wang, “A review of industrial wireless networks in the context of industry 4.0,” Wireless networks, vol. 23, No. 1, pp. 23-41, 2017. [cited by applicant]
C. Qian, Y. Zhang, C. Jiang, S. Pan, and Y. Rong, “A real-time datadriven collaborative mechanism in fixed-position assembly systems for smart manufacturing,” Robotics and Computer-Integrated Manufacturing, vol. 61, p. … [cited by applicant]
L. Zhao and K. Chen, “The game theoretic consensus in a networked multi-agent system,” in 2018 IEEE Global Communications Conference (GLOBECOM). IEEE, 2018, pp. 1-7. [cited by applicant]
E. Genender, C. L. Holloway, K. A. Remley, J. M. Ladbury, G. Koepke, and H. Garbe, “Simulating the multipath channel with a reverberation chamber: Application to bit error rate measurements,” IEEE Transactions on Electr… [cited by applicant]