journal article·2022-04-15Open access

An Online Task-Planning Framework Using Mixed Integer Programming for Multiple Cooking Tasks Using a Dual-Arm Robot

June-sup Yi, Tuan Anh Luong, Hosik Chae, Min Sung Ahn, Donghun Noh, Huy Nguyen Tran, Myeongyun Doh, Eugene Auh, Nabih Pico, Francisco Yumbla, Dennis Hong, Hyungpil Moon

Applied Sciences· Volume 12· Issue 8

Abstract

This work proposes an online task-scheduling method using mixed-integer programming for a multi-tasking problem regarding a dual-arm cooking robot in a controlled environment. Given each task’s processing time, their location in the working space, dependency, the required number of arms, and the kinematic constraints of the dual-arm robot, the proposed optimization algorithm can produce a feasible solution to scheduling the cooking order for each task and for each associated arms so that the total cooking time and the total moving distance for each arm are minimized. We use a subproblem optimization strategy in which the number of tasks to be planned is divided into several groups instead of planning all tasks at the same time. By doing so, the planning time can be significantly decreased, making the algorithm practical for online implementation. The feasibility of our optimization method and the effectiveness of the subproblem optimization strategy were verified through simulated experiments consisting of 30 to 120 tasks. The results showed that our strategy is advantageous in terms of computation time and makespan for large problems.
Source: crossref · Quality: baseline

Research context

OpenAlex topics: Advanced Manufacturing and Logistics Optimization · Scheduling and Optimization Algorithms · Robotic Path Planning Algorithms

SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.

Affiliations

Mechanical Engineering, Sungkyunkwan University, Seobu-ro, Suwon-si 2066, Korea

Mechanical and Aerospace Engineering, University of California, Los Angeles, CA 90095, USA

Facultad de Ingeniería en Electricidad y Computación, Escuela Superior Politécnica del Litoral, ESPOL, Campus Gustavo Galindo, Guayaquil 09-01-5863, Ecuador

Funding

Ministry of Trade, Industry and Energy

References (52)

Show source-provided references
1. Caldwell, D.G. (2012). Robotics and Automation in the Food Industry: Current and Future Technologies, Elsevier.
2. A simulation study of production task scheduling for a university cafeteria10.1177/1938965509347739 ↗
3. Cooking behavior with handling general cooking tools based on a system integration for a life-sized humanoid robot
4. Bollini, M., Tellex, S., Thompson, T., Roy, N., and Rus, D. (2013). Interpreting and Executing Recipes with a Cooking Robot, Springer. Experimental Robotics.10.1007/978-3-319-00065-7_33 ↗
5. Wang, H., Zhao, W., Li, B., Lin, X., and Zhang, D. (2009, January 13–19). Dynamic analysis and robust reliability design of pan mechanism for a cooking robot. Proceedings of the 2009 IEEE International Conference on Robotics and Biomimetics (ROBIO), Guilin, Guangxi.10.1109/ROBIO.2009.5420540 ↗
6. Beetz, M., Klank, U., Kresse, I., Maldonado, A., Mösenlechner, L., Pangercic, D., Rühr, T., and Tenorth, M. (2011, January 26–28). Robotic roommates making pancakes. Proceedings of the 2011 11th IEEE-RAS International Conference on Humanoid Robots, Bled, Slovenia.10.1109/Humanoids.2011.6100855 ↗
7. Inagawa, M., Takei, T., and Imanishi, E. (2020, January 12–15). Japanese Recipe Interpretation for Motion Process Generation of Cooking Robot. Proceedings of the 2020 IEEE/SICE International Symposium on System Integration (SII), Honolulu, HI, USA.10.1109/SII46433.2020.9026253 ↗
8. (2022, March 14). (ENG) ‘CLOi’s Table Zone’, Futuristic Restaurant at CES. 2020. YouTube. Available online: https://www.youtube.com/watch?v=vsZ_HUAPXL8.
9. (2022, March 14). Samsung Bot Chef at CES 2020. YouTube. Available online: https://www.youtube.com/watch?v=OwA6-b1Z7aQ.
10. Aeronautiques, C., Howe, A., Knoblock, C., McDermott, I.D., Ram, A., Veloso, M., Weld, D., SRI, D.W., Barrett, A., and Christianson, D. (1998). PDDL|The Planning Domain Definition Language. Tech. Rep.
11. Primitive Action Based Combined Task and Motion Planning for the Service Robot10.3389/frobt.2022.713470 ↗
12. Task planning in robotics: An empirical comparison of PDDL-and ASP-based systems10.1631/FITEE.1800514 ↗
13. Manso, L.J., Bustos, P., Alami, R., Milliez, G., and Núnez, P. (2015, January 5). Planning human–robot interaction tasks using graph models. Proceedings of the International Workshop on Recognition and Action for Scene Understanding (REACTS 2015), Malta, Malta.
14. Ayunts, E., and Panov, A.I. (2017). Task planning in “Block World” with deep reinforcement learning. First International Early Research Career Enhancement School on Biologically Inspired Cognitive Architectures, Springer.10.1007/978-3-319-63940-6_1 ↗
15. Lee, H. (2021). Learning Representations and Models of the World for Solving Complex Tasks, NVIDIA.
16. Machine learning for combinatorial optimization: A methodological tour d’horizon10.1016/j.ejor.2020.07.063 ↗
17. A survey on mixed-integer programming techniques in bilevel optimization10.1016/j.ejco.2021.100007 ↗
18. Portfolio problems with two levels decision-makers: Optimal portfolio selection with pricing decisions on transaction costs10.1016/j.ejor.2019.12.039 ↗
19. A mixed integer programming approach to the patient admission scheduling problem10.1016/j.ejor.2018.09.003 ↗
20. Decision rule bounds for two-stage stochastic bilevel programs10.1137/16M1098486 ↗
21. Lima, R.M., and Grossmann, I.E. (2011). Computational Advances in Solving Mixed Integer Linear Programming Problems, AIDAC.
22. Optimal cyclic multi-hoist scheduling: A mixed integer programming approach10.1287/opre.1040.0144 ↗
23. Batch versus cyclic scheduling of flexible flow shops by mixed-integer programming10.1080/00207543.2011.627388 ↗
24. An improved mixed integer programming approach for multi-hoist cyclic scheduling problem10.1109/TASE.2013.2254713 ↗
25. Yi, J.S., Ahn, M.S., Chae, H., Nam, H., Noh, D., Hong, D., and Moon, H. (2020, January 22–26). Task Planning with Mixed-Integer Programming for Multiple Cooking Task Using dual-arm Robot. Proceedings of the 2020 17th International Conference on Ubiquitous Robots (UR), Kyoto, Japan.10.1109/UR49135.2020.9144803 ↗
26. Ant colony optimization combined with taboo search for the job shop scheduling problem10.1016/j.cor.2006.07.003 ↗
27. A hybrid artificial bee colony algorithm for the job shop scheduling problem10.1016/j.ijpe.2012.03.035 ↗
28. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem10.1007/s00170-011-3610-1 ↗
29. Conventional genetic algorithm for job shop problems
30. A genetic algorithm for the job shop problem10.1016/0305-0548(93)E0015-L ↗
31. A hybrid particle swarm optimization for job shop scheduling problem10.1016/j.cie.2006.09.002 ↗
32. An efficient job-shop scheduling algorithm based on particle swarm optimization10.1016/j.eswa.2009.08.015 ↗
33. Flexible job-shop scheduling with parallel variable neighborhood search algorithm10.1016/j.eswa.2009.06.007 ↗
34. Multi-objective scheduling of dynamic job shop using variable neighborhood search10.1016/j.eswa.2009.05.001 ↗
35. The shifting bottleneck procedure for job shop scheduling10.1287/mnsc.34.3.391 ↗
36. Solution-guided multi-point constructive search for job shop scheduling10.1613/jair.2169 ↗
37. Combining constraint programming and local search for job-shop scheduling10.1287/ijoc.1100.0388 ↗
38. Solving the job-shop scheduling problem optimally by dynamic programming10.1016/j.cor.2012.02.024 ↗
39. Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem10.1016/j.cie.2020.106347 ↗
40. Mixed integer programming models for job shop scheduling: A computational analysis10.1016/j.cor.2016.04.006 ↗
41. Mixed binary integer programming formulations for the reentrant job shop scheduling problem10.1016/j.cor.2003.10.004 ↗
42. A goal programming network for mixed integer linear programming: A case study for the job-shop scheduling problem10.1142/S0129065791000182 ↗
43. An improved formulation for the job-shop scheduling problem10.1057/jors.1992.162 ↗
44. (2022, March 14). our over Coffee Drip Brewing Guide—How to Make Pour over Coffee. Blue Bottle Coffee. Available online: https://bluebottlecoffee.com/brew-guides/pour-over.
45. (2022, March 14). Chinese Chicken Salad. The Cheesecake Factory. Available online: https://www.thecheesecakefactory.com/recipes/chinese-chicken-salad.
46. Zacharias, F., Borst, C., and Hirzinger, G. (November, January 29). Capturing robot workspace structure: Representing robot capabilities. Proceedings of the 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, San Diego, CA, USA.10.1109/IROS.2007.4399105 ↗
47. Jang, K., Kim, S., and Park, J. (2021). Reactive Self-Collision Avoidance for a Differentially Driven Mobile Manipulator. Sensors, 21.10.3390/s21030890 ↗
48. Wolsey, L.A., and Nemhauser, G.L. (1999). Integer and Combinatorial Optimization, John Wiley & Sons.
49. Coordinating multiple robots with kinodynamic constraints along specified paths10.1177/0278364905051974 ↗
50. Andersen, E.D., and Andersen, K.D. (2000). The MOSEK interior point optimizer for linear programming: An implementation of the homogeneous algorithm. High Performance Optimization, Springer.10.1007/978-1-4757-3216-0_8 ↗
51. Noh, D., Liu, Y., Rafeedi, F., Nam, H., Gillespie, K., Yi, J.S., Zhu, T., Xu, Q., and Hong, D. (2020, January 22–26). Minimal Degree of Freedom Dual-Arm Manipulation Platform with Coupling Body Joint for Diverse Cooking Tasks. Proceedings of the 2020 17th International Conference on Ubiquitous Robots (UR), Kyoto, Japan.10.1109/UR49135.2020.9144811 ↗
52. Paek, J.H., and Lee, T.E. (2008, January 23–26). Optimal scheduling of dual-armed cluster tools without swap restriction. Proceedings of the 2008 IEEE International Conference on Automation Science and Engineering, Washington, DC, USA.