Path planning for production robots has been investigated. The sequence of the orders to be processed in a certain planning horizon has been planned for the production system.
Production automatic robots are employed to carry parts and products among all production stations and machining centers. The combination of machines in stations and autonomous robot evolves a production network.
The problem is to assign orders to robots so that paths are obtained to minimize total waiting times of production system and meanwhile provide collision-free paths.
The proposed mathematical formulation is implemented to show the efficiency and effectiveness.
Open Peer Review Details | |||
---|---|---|---|
Manuscript submitted on 26-10-2018 |
Original Manuscript | An Effective Mathematical Programming Model for Production Automatic Robot Path Planning |
Traditionally, Autonomous Guided Vehicles (AGVs) were mostly used at manufacturing systems, but currently, other applications of AGVs are extensively developed in other areas, such as warehouses, container terminals and transportation systems. The problem of path planning for AGV is a significant case while multiple AGVs are employed in the system [1T. Sasaki, G. Enriquez, T. Miwa, and S. Hashimoto, "Adaptive path planning for cleaning robots considering dust distribution", J. Robot. Mechatron., vol. 30, no. 1, pp. 5-14.
[http://dx.doi.org/10.20965/jrm.2018.p0005] -3M. Kitamura, Y. Yasuoka, T. Suzuki, Y. Amano, and T. Hashizume, "Path planning for autonomous vehicles using QZSS and satellite visibility map", J. Robot. Mechatron., vol. 25, no. 2, pp. 400-407.
[http://dx.doi.org/10.20965/jrm.2013.p0400] ]. An Automated Manufacturing System (AMS) is a complex network of machines and devices so that demands are fulfilled and production tasks are determined for all components accordingly [4S. Hoshino, and K. Uchida, "Interactive motion planning for mobile robot navigation in dynamic environments", J. Adv. Comput. Intell. Intell. Inform., vol. 21, no. 4, pp. 667-674.
[http://dx.doi.org/10.20965/jaciii.2017.p0667] ].
For the methods and techniques of path planning, different aspects are studied in the past. Unlike previous stochastic optimization methods which use expected values instead of probability distribution as length or cost of each arc in stochastic methods [5M.H. Olya, B. Shirazi, and H. Fazlollahtabar, "Adapted dynamic program to find shortest path in a network having normal probability distribution arc length", Adv Ind Eng Manage, vol. 2, no. 1, pp. 5-10.] proposed a novel general stochastic dynamic programming approach which is not only a dynamic method instead of a being static method but also it generates integrated probability functions at the end of each path in networks and compares probability distributions instead of expected values of each arc to find the shortest path in the network. In addition [6M.H. Olya, "Finding shortest path in a combined exponential–gamma probability distribution arc length", Int. J. Operat. Res., vol. 21, no. 1, pp. 25-37.
[http://dx.doi.org/10.1504/IJOR.2014.064020] ], implemented his method on different combinations of probability distributions and compared the results based on cost criterion to show the superiority of his developed method [7M.H. Olya, and H. Fazlollahtabar, "Finding shortest path in a combined exponential-gamma-normal probability distribution arc length", Adv Ind Eng Manage, vol. 3, no. 4, pp. 35-44., 8M. Olya, H. Fazlollahtabar, and I. Mahdavi, "Shortest path problem with gamma probability distribution arc length", Int J Operat Res, vol. 2, no. 4, pp. 55-66.]. Olya [9M.H. Olya, "Applying Dijkstra’s algorithm for general shortest path problem with normal probability distribution arc length", Int J. Operat Res, vol. 21, no. 2, pp. 143-154.
[http://dx.doi.org/10.1504/IJOR.2014.064541] ] analyzed the computational efficiency of the developed algorithm using maximum likelihood estimation and moment generating function in a simulation environment.
The effect of delay on path planning is significant due to the impact of on-time delivery for customer satisfaction. Also, collision-free decision making is challenging and leads to incur delay on the production schedule. Thus, the trade-off between delay and collision needs to be considered for optimal path planning.
In this paper, a general path planning mathematical model for autonomous production robot system has been proposed in a network. The aim of the model is to minimize the delay and thus the costs of transportation. The remainder of our work follows here. Next, the related literature is reviewed. In Section 3, the problem is justified and described. In Section 4, the proposed mathematical programming approach has been discussed. Numerical experiments are presented in Section 5. Conclusion is presented in Section 6.
In the literature, researchers investigated the design of an AMS and planning for the components being employed.
Fazlollahtabar and Saidi-Mehrabad [10H. Fazlollahtabar, and M. Saidi-Mehrabad, "Methodologies to optimize automated guided vehicle scheduling and routing problems: A review study", J. Intell. Robot. Syst., vol. 77, pp. 525-545.
[http://dx.doi.org/10.1007/s10846-013-0003-8] ] categorized the related literature for different scheduling and routing methods of autonomous robots in different problems such as distribution, transshipment and transportation systems.
Fazlollahtabar et al. [11H. Fazlollahtabar, B. Rezaie, and H. Kalantari, "Mathematical programming approach to optimize material flow in an AGV-based flexible jobshop manufacturing system with performance analysis", Int. J. Adv. Manuf. Technol., vol. 51, no. 9-12, pp. 1149-1158.
[http://dx.doi.org/10.1007/s00170-010-2700-9] ] analyzed material flow optimization for a flexible job shop automated manufacturing system. The aim was to balance the material flow carried by robots through the production stations. M’Hallah [12R. M’Hallah, "Minimizing total earliness and tardiness on a single machine using a hybrid heuristic", Comput. Oper. Res., vol. 34, pp. 3126-3142.
[http://dx.doi.org/10.1016/j.cor.2005.11.021] ] investigated job scheduling having different processing times and similar due dates on a single machine for total tardiness and earliness minimization. Ueno et al. [13K. Ueno, T. Kinoshita, K. Kobayashi, and K. Watanabe, "Development of a robust path-planning algorithm using virtual obstacles for an autonomous mobile robot", J. Robot. Mechatron., vol. 27, no. 3, pp. 286-292.
[http://dx.doi.org/10.20965/jrm.2015.p0286] ] considered the concept of virtual obstacles in path planning problem and developed a robust algorithm for optimization. Gerstl and Mosheiov [14E. Gerstl, and G. Mosheiov, "Scheduling problems with two competing agents to minimized weighted earliness–tardiness", Comput. Oper. Res., vol. 40, pp. 109-116.
[http://dx.doi.org/10.1016/j.cor.2012.05.019] ] considered scheduling problem for competing agents being processed on the same machine and developed a solution algorithm. Igari et al. [15S. Igari, F. Tanaka, and M. Onosato, "Computer-aided operation planning for an actual machine tool based on updatable machining database and database-oriented planning algorithm", Int. J. Automot. Technol., vol. 6, no. 6, pp. 717-723.
[http://dx.doi.org/10.20965/ijat.2012.p0717] ] developed a computer-aided operation planning for machines and tools based on database data retrieval concept. Mi’radj Isnaini and Shirase [16M. Mi’radj Isnaini, and K. Shirase, "Review of computer-aided process planning systems for machining operation – future development of a computer-aided process planning system", Int. J. Automot. Technol., vol. 8, no. 3, pp. 317-332.
[http://dx.doi.org/10.20965/ijat.2014.p0317] ] studied general process planning using computer-aided mechanism. Hamidinia et al [17A. Hamidinia, S. Khakabimamaghani, M. Mahdavi Mazdeh, and M. Jafari, "A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system", Comput. Ind. Eng., vol. 62, pp. 29-38.
[http://dx.doi.org/10.1016/j.cie.2011.08.014] ] considered a novel complex single-machine scheduling problem and proposed two solution methods. Fazlollahtabar and Mahdavi-Amiri [18H. Fazlollahtabar, and N. Mahdavi-Amiri, "Producer’s behavior analysis in an uncertain bicriteria AGV-based flexible jobshop manufacturing system with expert system", Int. J. Adv. Manuf. Technol., vol. 65, no. 9/12, pp. 1605-1618.
[http://dx.doi.org/10.1007/s00170-012-4283-0] ] proposed a bi-criteria optimal path planning in a flexible jobshop manufacturing system. Their model was associated with a comprehensive analytical study on the optimality of the hierarchical decision made by the optimal path method. Fazlollahtabar and Mahdavi-Amiri [19H. Fazlollahtabar, and N. Mahdavi-Amiri, "Design of a neuro-fuzzy–regression expert system to estimate cost in a flexible jobshop automated manufacturing system", Int. J. Adv. Manuf. Technol., vol. 67, no. 5/8, pp. 1809-1823.
[http://dx.doi.org/10.1007/s00170-012-4610-5] ] designed a cost estimation expert system using a fuzzy rule backpropagation network that provided the cost estimation in an uncertain autonomous production network. Fazlollahtabar and Olya [20H. Fazlollahtabar, and M.H. Olya, "A cross-entropy heuristic statistical modeling for determining total stochastic material handling time", Int. J. Adv. Manuf. Technol., vol. 67, no. 5/8, pp. 1631-1641.
[http://dx.doi.org/10.1007/s00170-012-4596-z] ] proposed a heuristic statistical method to compute the total stochastic material handling times by autonomous robots and to find an optimal path for an advanced production system.
Yokozuka and Matsumoto [21M. Yokozuka, and O. Matsumoto, "Reasonable path planning via path energy minimization", J. Robot. Mechatron., vol. 26, no. 2, pp. 236-244.
[http://dx.doi.org/10.20965/jrm.2014.p0236] ] investigated energy minimization path planning problem where robot energy consumption was significant for tactical decision-making level. Fazlollahtabar et al. [22H. Fazlollahtabar, M. Saidi-Mehrabad, and J. Balakrishnan, "Mathematical optimization for earliness/tardiness minimization in a multiple automated guided vehicle manufacturing system via integrated heuristic algorithms", Robot. Auton. Syst., vol. 72, pp. 131-138.
[http://dx.doi.org/10.1016/j.robot.2015.05.002] ] considered due dates of multiple autonomous robots as a criterion to analyze delay composing of earliness and tardiness; then an integrated heuristic algorithm was developed as a solution method.
Fazlollahtabar et al. [23H. Fazlollahtabar, M. Saidi-Mehrabad, and E. Masehian, "Mathematical model for deadlock resolution in multiple AGV scheduling and routing network: A case study. Industrial Robot", Int. J., vol. 42, no. 3, pp. 252-263.] introduced a new concept of a turning point and developed a complicated problem of concurrent routing and scheduling for multiple autonomous production robots. The aim was to provide conflict-free and deadlock resolution.
Ishikawa et al. [24K. Ishikawa, Y. Amano, and T. Hashizume, "Path planning for mobile mapping system considering the geometry of the GPS satellite", J. Robot. Mechatron., vol. 25, no. 3, pp. 545-552.
[http://dx.doi.org/10.20965/jrm.2013.p0545] ] analyzed the problem of path planning with respect to the geometry of the agents. For further studies on path planning problems and methods, the readers refer to Fazlollahtabar and Saidi-Mehrabad [25H. Fazlollahtabar, and M. Saidi-Mehrabad, "Autonomous guided vehicles: Methods and models for optimal path planning", Springer Int Publ Switzerland, .
[http://dx.doi.org/10.1007/978-3-319-14747-5] ].
A production system that contains several machining centers is considered. In any machining center, different types of machines exist to process the required tasks according to the process plan. Robots are used to carry parts to be machined amongst the machining centers and their corresponding machines. A network of machines and paths is configured so that robots move on the paths. The sequence of independent operations is pre-specified. The machines positioned in the same machining center have similar properties such as the same need of operator proficiency, similar functionality, and toolbox resemblance. The objective is to find a path plan for each production robot minimizing total waiting time while the costly collision of robots is avoided. The assignment of orders to robots is handled using a mathematical model. An overview of the problem is depicted in Fig. (1).
While several robots function in the proposed production, network challenges of robot collision are inevitable. The repair and downtime incur extra costs to the system and lead to backlogs of orders and lost sales. Another issue is the violation of cycle time which directly influences the demand satisfaction. Therefore, developing a mathematical model to handle collisions in robot path planning could be significant.
To formulate the proposed path plan, the due date for delivering a part to a machining center is considered to be the earliest processing time and the upper bound is the cycle time of the production system. Any time out of that window is assigned a penalty cost. In other words, if the robot delivers earlier than the lower bound then an earliness penalty is assigned and if it arrives later than the upper bound then a lateness penalty cost is incurred.
In the beginning, robots are parked at the parking lot. Then, machining centers call robots for handling the parts among the machining centers according to the process plan. The robots may occupy the same paths and collide. Then the path plan should be triggered to prevent the collision of robots. On the other hand, the robots should be allocated to the paths so that waiting times are minimized. Thus, a mathematical model is proposed to both prevent collision and minimize the total waiting times of robots.
In this problem, robots should arrive at a machining center within its due date window to handle the transfer action otherwise:
Fig. (1) An overview of the problem. |
The mathematical notations are listed below.
Assignment of vth robot to a path connecting ith and jth machining centers
A slack variable t_{i}_{v} shows the arrival time of vth robot to ith machining center.
(1) |
which is minimizing the transportation cost and delay penalties. The first term of the objective function is to compute the vth robot movement cost between ith and jth machining centers. The second term is minimizing the delay penalties of robots arrival to machining centers.
(2) |
The constraint is related to interval time for robot which is to determine the robot arrival time to a machining center.
(3) |
The constraint certifies that each entering robot to a machining center will certainly exit (note that p is a counter for machining centers).
(4) |
The constraint expresses that robots are located at central machining center sent to a machining center to process handling task and after that return to the original position. By 0 the model shows the robots parking machining center.
(5) |
The constraint certifies for each movement between any two machining centers, only one robot is assigned.
(6) |
(7) |
The two constraints certify that only one arc is entered and exited from a machining center (n is the number of machining centers).
(8) |
The relation shows the type of decision variable.
Here, to implement the proposed mathematical model of path planning, a numerical example is presented. Here, a medium sized problem with the following specifications is designed:
Number of machining centers: 8,
Number of robots: 3,
Average velocity of robots: 3m/s,
Unit costs of traveling are 5, 9, 11, for all robots, respectively,
The distances among all machining centers are a 8*8 matrix:
d= 0, 2, 4, 5, 7, 8, 10, 14,
2, 0, 1, 2, 6, 7, 9, 13,
4, 1, 0, 3, 4, 5, 10, 12,
5, 2, 3, 0, 2, 6, 11, 14,
7, 6, 4, 2, 0, 1, 4, 7,
8, 7, 5, 6, 1, 0, 3, 5,
10, 9, 10, 11, 4, 3, 0, 4,
14, 13, 12, 14, 7, 5, 4, 0;
Robots should arrive at a machining center in the due time to handle the material to the next machining center. If it arrives early or late then a waiting time is incurred and penalized by a cost of Pl=7.
Using the above data, we optimized the mathematical model in GAMS software. The obtained decision variables resulted from GAMS optimization software, are shown below in Table 1.
The objective function value obtained from the mathematical model is 72. The assignment of robots to machining centers and the path plan is shown in Fig. (2).
Fig. (2) Path plan for the example. |
Fig. (2) shows that the first robot is assigned to machining center 1 and then takes the parts to center 2, 3 and 4, respectively and then moves to the depot. Then, robot 2 is allocated to machining center 7 and moves to 6, 5 and finally to the depot. Robot 3 is also called from machining center 8 and takes the final product to the depot.
A comparative analysis is performed to verify the efficiency of the proposed model. It has beenet al. considered to increase the delay penalty cost and run the model again to investigate the effects. Here, the penalty is increased to 12 unit of const. Then, the objective function value is 68; the reason is that the model obliges the robots and machines not to have a delay as much as possible.
In the second experiment, we decrease the distances between any two machining centers and evaluate the outputs of the model. The results show that the objective function value is increased to 85 and the reason is the impact of collision regarding shorted distances leading to more delays.
Therefore, the model is valid for different circumstances.
This paper formulated the robot path planning problem in a production system having multiple robots and machining centers in a network configuration. The waiting time, lateness, and collision were considered in the model. The objective was to provide paths having a minimal delay and moving costs for different robots. The main contributions of the problem include collision challenge in the modeling, and considering delay concept for robots. An illustrative example worked out to imply the applicability of the mathematical model. The results showed that the optimal assignments of robots to paths provide minimal distance moved by robots and minimal delay composing of delays. For future research, the following suggestions are recommended:
Not applicable.
The author declares no conflict of interest, financial or otherwise.
Declared none.
[1] | T. Sasaki, G. Enriquez, T. Miwa, and S. Hashimoto, "Adaptive path planning for cleaning robots considering dust distribution", J. Robot. Mechatron., vol. 30, no. 1, pp. 5-14. [http://dx.doi.org/10.20965/jrm.2018.p0005] |
[2] | H. Darweesh, E. Takeuchi, K. Takeda, Y. Ninomiya, A. Sujiwo, L. Yoichi Morales, N. Akai, T. Tomizawa, and S. Kato, "Open source integrated planner for autonomous navigation in highly dynamic environments", J. Robot. Mechatron., vol. 29, no. 4, pp. 668-684. [http://dx.doi.org/10.20965/jrm.2017.p0668] |
[3] | M. Kitamura, Y. Yasuoka, T. Suzuki, Y. Amano, and T. Hashizume, "Path planning for autonomous vehicles using QZSS and satellite visibility map", J. Robot. Mechatron., vol. 25, no. 2, pp. 400-407. [http://dx.doi.org/10.20965/jrm.2013.p0400] |
[4] | S. Hoshino, and K. Uchida, "Interactive motion planning for mobile robot navigation in dynamic environments", J. Adv. Comput. Intell. Intell. Inform., vol. 21, no. 4, pp. 667-674. [http://dx.doi.org/10.20965/jaciii.2017.p0667] |
[5] | M.H. Olya, B. Shirazi, and H. Fazlollahtabar, "Adapted dynamic program to find shortest path in a network having normal probability distribution arc length", Adv Ind Eng Manage, vol. 2, no. 1, pp. 5-10. |
[6] | M.H. Olya, "Finding shortest path in a combined exponential–gamma probability distribution arc length", Int. J. Operat. Res., vol. 21, no. 1, pp. 25-37. [http://dx.doi.org/10.1504/IJOR.2014.064020] |
[7] | M.H. Olya, and H. Fazlollahtabar, "Finding shortest path in a combined exponential-gamma-normal probability distribution arc length", Adv Ind Eng Manage, vol. 3, no. 4, pp. 35-44. |
[8] | M. Olya, H. Fazlollahtabar, and I. Mahdavi, "Shortest path problem with gamma probability distribution arc length", Int J Operat Res, vol. 2, no. 4, pp. 55-66. |
[9] | M.H. Olya, "Applying Dijkstra’s algorithm for general shortest path problem with normal probability distribution arc length", Int J. Operat Res, vol. 21, no. 2, pp. 143-154. [http://dx.doi.org/10.1504/IJOR.2014.064541] |
[10] | H. Fazlollahtabar, and M. Saidi-Mehrabad, "Methodologies to optimize automated guided vehicle scheduling and routing problems: A review study", J. Intell. Robot. Syst., vol. 77, pp. 525-545. [http://dx.doi.org/10.1007/s10846-013-0003-8] |
[11] | H. Fazlollahtabar, B. Rezaie, and H. Kalantari, "Mathematical programming approach to optimize material flow in an AGV-based flexible jobshop manufacturing system with performance analysis", Int. J. Adv. Manuf. Technol., vol. 51, no. 9-12, pp. 1149-1158. [http://dx.doi.org/10.1007/s00170-010-2700-9] |
[12] | R. M’Hallah, "Minimizing total earliness and tardiness on a single machine using a hybrid heuristic", Comput. Oper. Res., vol. 34, pp. 3126-3142. [http://dx.doi.org/10.1016/j.cor.2005.11.021] |
[13] | K. Ueno, T. Kinoshita, K. Kobayashi, and K. Watanabe, "Development of a robust path-planning algorithm using virtual obstacles for an autonomous mobile robot", J. Robot. Mechatron., vol. 27, no. 3, pp. 286-292. [http://dx.doi.org/10.20965/jrm.2015.p0286] |
[14] | E. Gerstl, and G. Mosheiov, "Scheduling problems with two competing agents to minimized weighted earliness–tardiness", Comput. Oper. Res., vol. 40, pp. 109-116. [http://dx.doi.org/10.1016/j.cor.2012.05.019] |
[15] | S. Igari, F. Tanaka, and M. Onosato, "Computer-aided operation planning for an actual machine tool based on updatable machining database and database-oriented planning algorithm", Int. J. Automot. Technol., vol. 6, no. 6, pp. 717-723. [http://dx.doi.org/10.20965/ijat.2012.p0717] |
[16] | M. Mi’radj Isnaini, and K. Shirase, "Review of computer-aided process planning systems for machining operation – future development of a computer-aided process planning system", Int. J. Automot. Technol., vol. 8, no. 3, pp. 317-332. [http://dx.doi.org/10.20965/ijat.2014.p0317] |
[17] | A. Hamidinia, S. Khakabimamaghani, M. Mahdavi Mazdeh, and M. Jafari, "A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system", Comput. Ind. Eng., vol. 62, pp. 29-38. [http://dx.doi.org/10.1016/j.cie.2011.08.014] |
[18] | H. Fazlollahtabar, and N. Mahdavi-Amiri, "Producer’s behavior analysis in an uncertain bicriteria AGV-based flexible jobshop manufacturing system with expert system", Int. J. Adv. Manuf. Technol., vol. 65, no. 9/12, pp. 1605-1618. [http://dx.doi.org/10.1007/s00170-012-4283-0] |
[19] | H. Fazlollahtabar, and N. Mahdavi-Amiri, "Design of a neuro-fuzzy–regression expert system to estimate cost in a flexible jobshop automated manufacturing system", Int. J. Adv. Manuf. Technol., vol. 67, no. 5/8, pp. 1809-1823. [http://dx.doi.org/10.1007/s00170-012-4610-5] |
[20] | H. Fazlollahtabar, and M.H. Olya, "A cross-entropy heuristic statistical modeling for determining total stochastic material handling time", Int. J. Adv. Manuf. Technol., vol. 67, no. 5/8, pp. 1631-1641. [http://dx.doi.org/10.1007/s00170-012-4596-z] |
[21] | M. Yokozuka, and O. Matsumoto, "Reasonable path planning via path energy minimization", J. Robot. Mechatron., vol. 26, no. 2, pp. 236-244. [http://dx.doi.org/10.20965/jrm.2014.p0236] |
[22] | H. Fazlollahtabar, M. Saidi-Mehrabad, and J. Balakrishnan, "Mathematical optimization for earliness/tardiness minimization in a multiple automated guided vehicle manufacturing system via integrated heuristic algorithms", Robot. Auton. Syst., vol. 72, pp. 131-138. [http://dx.doi.org/10.1016/j.robot.2015.05.002] |
[23] | H. Fazlollahtabar, M. Saidi-Mehrabad, and E. Masehian, "Mathematical model for deadlock resolution in multiple AGV scheduling and routing network: A case study. Industrial Robot", Int. J., vol. 42, no. 3, pp. 252-263. |
[24] | K. Ishikawa, Y. Amano, and T. Hashizume, "Path planning for mobile mapping system considering the geometry of the GPS satellite", J. Robot. Mechatron., vol. 25, no. 3, pp. 545-552. [http://dx.doi.org/10.20965/jrm.2013.p0545] |
[25] | H. Fazlollahtabar, and M. Saidi-Mehrabad, "Autonomous guided vehicles: Methods and models for optimal path planning", Springer Int Publ Switzerland, . [http://dx.doi.org/10.1007/978-3-319-14747-5] |