April  2017, 13(2): 835-856. doi: 10.3934/jimo.2016049

An optimal algorithm for the obstacle neutralization problem

1. 

Computer Engineering Department, Marmara University, Istanbul, 34722, Turkey

2. 

Software Engineering Department, Yasar University, Izmir, 35100, Turkey

Received  April 2015 Revised  December 2015 Published  August 2016

In this study, an optimal algorithm is presented for the obstacle neutralization problem (ONP). ONP is a recently introduced path planning problem wherein an agent needs to swiftly navigate from a source to a destination through an arrangement of obstacles in the plane. The agent has a limited neutralization capability in the sense that the agent can safely pass through an obstacle upon neutralization at a cost added to the traversal length. The goal of an agent is to find the sequence of obstacles to be neutralized en route minimizing the overall traversal length subject to the neutralization limit. Our optimal algorithm consists of two phases. In the first phase an upper bound of the problem is obtained using a suboptimal algorithm. In the second phase, starting from the bound obtained from phase Ⅰ, a $k$-th shortest path algorithm is exploited to find the optimal solution. The performance of the algorithm is presented with computational experiments conducted both on real and synthetic naval minefield data. Results are promising in the sense that the proposed method can be applied in online applications.

Citation: Ali Fuat Alkaya, Dindar Oz. An optimal algorithm for the obstacle neutralization problem. Journal of Industrial & Management Optimization, 2017, 13 (2) : 835-856. doi: 10.3934/jimo.2016049
References:
[1]

V. Aksakalli and I. Ari, Penalty-based algorithms for the stochastic obstacle scene problem, INFORMS Journal on Computing, 26 (2014), 370-384.  doi: 10.1287/ijoc.2013.0571.  Google Scholar

[2]

V. Aksakalli and E. Ceyhan, Optimal obstacle placement with disambiguations, Annals of Applied Statistics, 6 (2012), 1730-1774.  doi: 10.1214/12-AOAS556.  Google Scholar

[3]

V. AksakalliD. FishkindC. E. Priebe and X. Ye, The reset disambiguation policy for navigating stochastic obstacle fields, Naval Research Logistics, 58 (2011), 389-399.  doi: 10.1002/nav.20454.  Google Scholar

[4]

R. Algin, A. F. Alkaya, V. Aksakalli and D. Oz, 2013. An ant system algorithm for the neutralization problem, Advances in Computational Intelligence, Volume 7903 of the series Lecture Notes in Computer Science, (2013), 53–61. doi: 10.1007/978-3-642-38682-4_7.  Google Scholar

[5]

R. Algin and A. F. Alkaya, Solving the obstacle neutralization problem using swarm intelligence algorithms, Proceedings of 7th International Conference on Soft Computing and Pattern Recognition, (2015), 187-192.  doi: 10.1109/SOCPAR.2015.7492805.  Google Scholar

[6]

A. F. Alkaya and R. Algin, Metaheuristic based solution approaches for the obstacle neutralization problem, Expert Systems with Applications, 42 (2015), 1094-1105.  doi: 10.1016/j.eswa.2014.09.027.  Google Scholar

[7]

A. F. AlkayaV. Aksakalli and C. E. Priebe, A penalty search algorithm for the obstacle neutralization problem, Computers and Operations Research, 53 (2015), 165-175.  doi: 10.1016/j.cor.2014.08.013.  Google Scholar

[8]

J. F. Bekker and J. P. Schmid, Planning the safe transit of a ship through a mapped minefield, Journal of the Operations Research Society of South Africa, 22 (2006), 1-18.  doi: 10.5784/22-1-30.  Google Scholar

[9]

W. M. CarlyleJ. O. Royset and R. K. Wood, Lagrangian relaxation and enumeration for solving constrained shortest-path problems, Networks, 52 (2008), 256-270.  doi: 10.1002/net.20247.  Google Scholar

[10]

Costal Battlefied Reconnaissance and Analysis -(COBRA), http://www.navy.mil/navydata/fact_display.asp?cid=2100&tid=1237&ct=2, Last access: September 1,2014. Google Scholar

[11]

G. Dahl and B. Realfsen, Curve Approximation and Constrained Shortest Path Problems, International Symposium on Mathematical Programming (ISMP97), 1997. Google Scholar

[12]

G. Dahl and B. Realfsen, Curve approximation constrained shortest path problems, Networks, 36 (2000), 1-8.  doi: 10.1002/1097-0037(200008)36:1<1::AID-NET1>3.0.CO;2-B.  Google Scholar

[13]

I. Dumitrescu and N. Boland, Algorithms for the weight constrained shortest path problem, International Transactions in Operational Research, 8 (2001), 15-29.  doi: 10.1111/1475-3995.00003.  Google Scholar

[14]

D. E. FishkindC. E. PriebeK. GilesL. N. Smith and V. Aksakalli, Disambiguation protocols based on risk simulation, IEEE Transactions on Systems, Man, and Cybernetics, Part A, 37 (2007), 814-823.  doi: 10.1109/TSMCA.2007.902634.  Google Scholar

[15]

L. Guo and I. Matta, Search space reduction in QoS routing, Computer Networks, 41 (2003), 73-88.  doi: 10.1016/S1389-1286(02)00344-4.  Google Scholar

[16]

G. Y. Handler and I. Zang, A dual algorithm for the constrained shortest path problem, Networks, 10 (1980), 293-309.  doi: 10.1002/net.3230100403.  Google Scholar

[17]

A. JüittnerB. SzviatovskiI. Mecs and Z. Rajko, Lagrange relaxation based method for the QoS routing problem, Proceedings of 20th Annual Joint Conference of the IEEE Computer Communications Societies, 2 (2001), 859-868.   Google Scholar

[18]

T. Koch, Rapid Mathematical Prototyping, Ph. D. Thesis, Technische Universität Berlin, 2004. Google Scholar

[19]

F. KuipersT. KorkmazM. Krunz and P. Van Mieghemt, Performance evaluation of constraint-based path selection algorithms, IEEE Network, 18 (2004), 16-23.  doi: 10.1109/MNET.2004.1337731.  Google Scholar

[20]

J. LatourellB. Wallet and B. Copeland, Genetic algorithm to solve constrained routing problem with applications for cruise missile routing, Proceedings of SPIE, 3390 (1998), 490-500.  doi: 10.1117/12.304839.  Google Scholar

[21]

S. H. K. Lee, Route Optimization Model for Strike Aircraft, Master's thesis, Naval Postgraduate School, Monterey, California, 1995. Google Scholar

[22]

P. C. Li, Planning the Optimal Transit for a Ship Through a Mapped Minefield, Master's thesis, Naval Postgraduate School, Monterey, California, 2009. Google Scholar

[23]

Y. M. MarghiF. Towhidkhah and S. Gharibzadeh, A two level real-time path planning method inspired by cognitive map and predictive optimization in human brain, Applied Soft Computing, 21 (2014), 352-364.  doi: 10.1016/j.asoc.2014.03.038.  Google Scholar

[24]

C. MouW. Qing-xian and J. Chang-sheng, A modified ant optimization algorithm for path planning of UCAV, Applied Soft Computing, 8 (2008), 1712-1718.  doi: 10.1016/j.asoc.2007.10.011.  Google Scholar

[25]

R. MuhandiramgeN. Boland and S. Wang, Convergent network approximation for the continuous euclidean length constrained minimum cost path problem, SIAM journal on Optimization, 20 (2009), 54-77.  doi: 10.1137/070695356.  Google Scholar

[26]

R. NygaardJ. HusZy and D. Haugland, Compression of image contours using combinatorial optimization, Proceedings of the International Conference on Image Processing-ICIP98, 1 (1998), 266-270.  doi: 10.1109/ICIP.1998.723470.  Google Scholar

[27]

C. E. PriebeD. E. FishkindL. Abrams and C. D. Piatko, Random disambiguation paths for traversing a mapped hazard field, Naval Research Logistics, 52 (2005), 285-292.  doi: 10.1002/nav.20071.  Google Scholar

[28]

C. E. PriebeT. E. Olson and D. M. Healy Jr., Exploiting stochastic partitions for minefield detection, Proceedings of the SPIE, 3079 (1997), 508-518.   Google Scholar

[29]

D. S. Reeves and H. F. Salama, A distributed algorithm for delay-constrained unicast routing, IEEE/ACM Transactions on Networking, 8 (2000), 239-250.  doi: 10.1109/90.842145.  Google Scholar

[30]

J. O. RoysetW. M. Carlyle and R. K. Wood, Routing military aircraft with a constrained shortest-path algorithm, Military Operations Research, 14 (2009), 31-52.   Google Scholar

[31]

N. H. WitherspoonJ. H. HollowayK. S. DavisR. W. Miller and A. C. Dubey, The coastal battlefield reconnaissance and analysis (cobra) program for minefield detection, Proceedings of the SPIE: Detection Technologies for Mines and Minelike Targets, Orlando, Florida, 2496 (1995), 500-508.   Google Scholar

[32]

B. YangY. DingY. Jin and K. Haho, Self-organized swarm robot for target search and trapping inspired by bacterial chemotaxis, Robotics and Autonomous Systems, 72 (2015), 83-92.  doi: 10.1016/j.robot.2015.05.001.  Google Scholar

[33]

X. YeD. E. Fishkind and C. E. Priebe, Sensor information monotonicity in disambiguation protocols, Journal of the Operational Research Society, 62 (2011), 142-151.  doi: 10.1057/jors.2009.152.  Google Scholar

[34]

X. Ye and C. E. Priebe, A graph-search based navigation algorithm for traversing a potentially hazardous area with disambiguation, International Journal of Operations Research and Information Systems, 1 (2010), 14-27.  doi: 10.4018/978-1-4666-0933-4.ch007.  Google Scholar

[35]

J. Y. Yen, Finding the k shortest loopless paths in a network, Management Science, 17 (1971), 712-716.   Google Scholar

[36]

M. ZabarankinS. Uryasev and R. Murphey, Aircraft routing under the risk of detection, Naval Research Logistics, 53 (2006), 728-747.  doi: 10.1002/nav.20165.  Google Scholar

[37]

M. ZabarankinS. Uryasev and P. Pardalos, Optimal risk path algorithms, Cooperative Control and Optimization (R. Murphey and P. Pardalos ed.), Kluwer Academic, Dordrecht, 66 (2002), 273-298.  doi: 10.1007/0-306-47536-7_13.  Google Scholar

[38]

Q. ZhuJ. HuW. Cai and L. Henschen, A new robot navigation algorithm for dynamic unknown environments based on dynamic path re-computation and an improved scout ant algorithm, Applied Soft Computing, 11 (2011), 4667-4676.  doi: 10.1016/j.asoc.2011.07.016.  Google Scholar

show all references

References:
[1]

V. Aksakalli and I. Ari, Penalty-based algorithms for the stochastic obstacle scene problem, INFORMS Journal on Computing, 26 (2014), 370-384.  doi: 10.1287/ijoc.2013.0571.  Google Scholar

[2]

V. Aksakalli and E. Ceyhan, Optimal obstacle placement with disambiguations, Annals of Applied Statistics, 6 (2012), 1730-1774.  doi: 10.1214/12-AOAS556.  Google Scholar

[3]

V. AksakalliD. FishkindC. E. Priebe and X. Ye, The reset disambiguation policy for navigating stochastic obstacle fields, Naval Research Logistics, 58 (2011), 389-399.  doi: 10.1002/nav.20454.  Google Scholar

[4]

R. Algin, A. F. Alkaya, V. Aksakalli and D. Oz, 2013. An ant system algorithm for the neutralization problem, Advances in Computational Intelligence, Volume 7903 of the series Lecture Notes in Computer Science, (2013), 53–61. doi: 10.1007/978-3-642-38682-4_7.  Google Scholar

[5]

R. Algin and A. F. Alkaya, Solving the obstacle neutralization problem using swarm intelligence algorithms, Proceedings of 7th International Conference on Soft Computing and Pattern Recognition, (2015), 187-192.  doi: 10.1109/SOCPAR.2015.7492805.  Google Scholar

[6]

A. F. Alkaya and R. Algin, Metaheuristic based solution approaches for the obstacle neutralization problem, Expert Systems with Applications, 42 (2015), 1094-1105.  doi: 10.1016/j.eswa.2014.09.027.  Google Scholar

[7]

A. F. AlkayaV. Aksakalli and C. E. Priebe, A penalty search algorithm for the obstacle neutralization problem, Computers and Operations Research, 53 (2015), 165-175.  doi: 10.1016/j.cor.2014.08.013.  Google Scholar

[8]

J. F. Bekker and J. P. Schmid, Planning the safe transit of a ship through a mapped minefield, Journal of the Operations Research Society of South Africa, 22 (2006), 1-18.  doi: 10.5784/22-1-30.  Google Scholar

[9]

W. M. CarlyleJ. O. Royset and R. K. Wood, Lagrangian relaxation and enumeration for solving constrained shortest-path problems, Networks, 52 (2008), 256-270.  doi: 10.1002/net.20247.  Google Scholar

[10]

Costal Battlefied Reconnaissance and Analysis -(COBRA), http://www.navy.mil/navydata/fact_display.asp?cid=2100&tid=1237&ct=2, Last access: September 1,2014. Google Scholar

[11]

G. Dahl and B. Realfsen, Curve Approximation and Constrained Shortest Path Problems, International Symposium on Mathematical Programming (ISMP97), 1997. Google Scholar

[12]

G. Dahl and B. Realfsen, Curve approximation constrained shortest path problems, Networks, 36 (2000), 1-8.  doi: 10.1002/1097-0037(200008)36:1<1::AID-NET1>3.0.CO;2-B.  Google Scholar

[13]

I. Dumitrescu and N. Boland, Algorithms for the weight constrained shortest path problem, International Transactions in Operational Research, 8 (2001), 15-29.  doi: 10.1111/1475-3995.00003.  Google Scholar

[14]

D. E. FishkindC. E. PriebeK. GilesL. N. Smith and V. Aksakalli, Disambiguation protocols based on risk simulation, IEEE Transactions on Systems, Man, and Cybernetics, Part A, 37 (2007), 814-823.  doi: 10.1109/TSMCA.2007.902634.  Google Scholar

[15]

L. Guo and I. Matta, Search space reduction in QoS routing, Computer Networks, 41 (2003), 73-88.  doi: 10.1016/S1389-1286(02)00344-4.  Google Scholar

[16]

G. Y. Handler and I. Zang, A dual algorithm for the constrained shortest path problem, Networks, 10 (1980), 293-309.  doi: 10.1002/net.3230100403.  Google Scholar

[17]

A. JüittnerB. SzviatovskiI. Mecs and Z. Rajko, Lagrange relaxation based method for the QoS routing problem, Proceedings of 20th Annual Joint Conference of the IEEE Computer Communications Societies, 2 (2001), 859-868.   Google Scholar

[18]

T. Koch, Rapid Mathematical Prototyping, Ph. D. Thesis, Technische Universität Berlin, 2004. Google Scholar

[19]

F. KuipersT. KorkmazM. Krunz and P. Van Mieghemt, Performance evaluation of constraint-based path selection algorithms, IEEE Network, 18 (2004), 16-23.  doi: 10.1109/MNET.2004.1337731.  Google Scholar

[20]

J. LatourellB. Wallet and B. Copeland, Genetic algorithm to solve constrained routing problem with applications for cruise missile routing, Proceedings of SPIE, 3390 (1998), 490-500.  doi: 10.1117/12.304839.  Google Scholar

[21]

S. H. K. Lee, Route Optimization Model for Strike Aircraft, Master's thesis, Naval Postgraduate School, Monterey, California, 1995. Google Scholar

[22]

P. C. Li, Planning the Optimal Transit for a Ship Through a Mapped Minefield, Master's thesis, Naval Postgraduate School, Monterey, California, 2009. Google Scholar

[23]

Y. M. MarghiF. Towhidkhah and S. Gharibzadeh, A two level real-time path planning method inspired by cognitive map and predictive optimization in human brain, Applied Soft Computing, 21 (2014), 352-364.  doi: 10.1016/j.asoc.2014.03.038.  Google Scholar

[24]

C. MouW. Qing-xian and J. Chang-sheng, A modified ant optimization algorithm for path planning of UCAV, Applied Soft Computing, 8 (2008), 1712-1718.  doi: 10.1016/j.asoc.2007.10.011.  Google Scholar

[25]

R. MuhandiramgeN. Boland and S. Wang, Convergent network approximation for the continuous euclidean length constrained minimum cost path problem, SIAM journal on Optimization, 20 (2009), 54-77.  doi: 10.1137/070695356.  Google Scholar

[26]

R. NygaardJ. HusZy and D. Haugland, Compression of image contours using combinatorial optimization, Proceedings of the International Conference on Image Processing-ICIP98, 1 (1998), 266-270.  doi: 10.1109/ICIP.1998.723470.  Google Scholar

[27]

C. E. PriebeD. E. FishkindL. Abrams and C. D. Piatko, Random disambiguation paths for traversing a mapped hazard field, Naval Research Logistics, 52 (2005), 285-292.  doi: 10.1002/nav.20071.  Google Scholar

[28]

C. E. PriebeT. E. Olson and D. M. Healy Jr., Exploiting stochastic partitions for minefield detection, Proceedings of the SPIE, 3079 (1997), 508-518.   Google Scholar

[29]

D. S. Reeves and H. F. Salama, A distributed algorithm for delay-constrained unicast routing, IEEE/ACM Transactions on Networking, 8 (2000), 239-250.  doi: 10.1109/90.842145.  Google Scholar

[30]

J. O. RoysetW. M. Carlyle and R. K. Wood, Routing military aircraft with a constrained shortest-path algorithm, Military Operations Research, 14 (2009), 31-52.   Google Scholar

[31]

N. H. WitherspoonJ. H. HollowayK. S. DavisR. W. Miller and A. C. Dubey, The coastal battlefield reconnaissance and analysis (cobra) program for minefield detection, Proceedings of the SPIE: Detection Technologies for Mines and Minelike Targets, Orlando, Florida, 2496 (1995), 500-508.   Google Scholar

[32]

B. YangY. DingY. Jin and K. Haho, Self-organized swarm robot for target search and trapping inspired by bacterial chemotaxis, Robotics and Autonomous Systems, 72 (2015), 83-92.  doi: 10.1016/j.robot.2015.05.001.  Google Scholar

[33]

X. YeD. E. Fishkind and C. E. Priebe, Sensor information monotonicity in disambiguation protocols, Journal of the Operational Research Society, 62 (2011), 142-151.  doi: 10.1057/jors.2009.152.  Google Scholar

[34]

X. Ye and C. E. Priebe, A graph-search based navigation algorithm for traversing a potentially hazardous area with disambiguation, International Journal of Operations Research and Information Systems, 1 (2010), 14-27.  doi: 10.4018/978-1-4666-0933-4.ch007.  Google Scholar

[35]

J. Y. Yen, Finding the k shortest loopless paths in a network, Management Science, 17 (1971), 712-716.   Google Scholar

[36]

M. ZabarankinS. Uryasev and R. Murphey, Aircraft routing under the risk of detection, Naval Research Logistics, 53 (2006), 728-747.  doi: 10.1002/nav.20165.  Google Scholar

[37]

M. ZabarankinS. Uryasev and P. Pardalos, Optimal risk path algorithms, Cooperative Control and Optimization (R. Murphey and P. Pardalos ed.), Kluwer Academic, Dordrecht, 66 (2002), 273-298.  doi: 10.1007/0-306-47536-7_13.  Google Scholar

[38]

Q. ZhuJ. HuW. Cai and L. Henschen, A new robot navigation algorithm for dynamic unknown environments based on dynamic path re-computation and an improved scout ant algorithm, Applied Soft Computing, 11 (2011), 4667-4676.  doi: 10.1016/j.asoc.2011.07.016.  Google Scholar

Figure 1.  An example to the obstacle neutralization problem and optimal paths for $K$ = 0, 1, 2 and 3
Figure 3.  An example that depicts the case where any path returned by kSPA satisfying the maximum allowed number of neutralizations constraint may not necessarily be the optimum path
Figure 4.  Optimal Algorithm
Figure 5.  Details for creating a TAG
Figure 6.  An actual naval minefield data set, called the COBRA data
Figure 7.  An example depicting the solutions on continuous space and discretized space at three different resolution settings
Figure 8.  An example how there occurs many parallel paths on a discretized minefield
Table 1.  Center coordinates of COBRA disks
X-coordinate Y-coordinate
321.17 158.27
215.13 428.31
221.12 557.31
163.31 186.14
100.40 376.47
116.39 110.84
-91.27 664.45
-19.93 568.04
-35.11 242.61
-78.75 396.14
-134.53 769.27
-219.32 313.68
-242.22 321.51
54.23 201.12
-145.67 703.06
-166.36 299.42
28.31 205.03
-105.75 262.40
-128.60 274.12
-82.87 348.29
-310.23 402.92
-169.99 438.90
-245.28 372.05
-258.45 641.03
-455.72 742.57
-237.86 546.19
158.17 516.48
-151.01 572.15
296.16 163.31
-79.26 709.99
185.31 182.18
-61.19 345.12
105.47 509.80
-320.73 532.23
95.39 248.12
-166.45 180.33
111.60 640.10
-157.10 441.96
-269.98 379.65
X-coordinate Y-coordinate
321.17 158.27
215.13 428.31
221.12 557.31
163.31 186.14
100.40 376.47
116.39 110.84
-91.27 664.45
-19.93 568.04
-35.11 242.61
-78.75 396.14
-134.53 769.27
-219.32 313.68
-242.22 321.51
54.23 201.12
-145.67 703.06
-166.36 299.42
28.31 205.03
-105.75 262.40
-128.60 274.12
-82.87 348.29
-310.23 402.92
-169.99 438.90
-245.28 372.05
-258.45 641.03
-455.72 742.57
-237.86 546.19
158.17 516.48
-151.01 572.15
296.16 163.31
-79.26 709.99
185.31 182.18
-61.19 345.12
105.47 509.80
-320.73 532.23
95.39 248.12
-166.45 180.33
111.60 640.10
-157.10 441.96
-269.98 379.65
Table 2.  Result on original and discretized COBRA data where several $C$ and $K$ value combinations are tried
C K Continuous Env. Discretized Env.
Proposed Optimal Algo. IP Solver Proposed Optimal Algo.
$\theta(p^*)$ $\tau(p^*)$ #RP RT (s) RT (s) $\theta(p^*)$ $\tau(p^*)$ #RP RT (s)
1 0 0 977.54 0 0.055 0.36 0 1043.26 0 0.078
1 1 708.97 0 0.055 3.34 1 758.99 0 0.051
2 2 704.83 0 0.042 4.38 2 726.85 0 0.086
3 3 703 0 0.009 4.04 3 711.28 0 0.034
5 0 0 977.54 0 0.041 0.48 0 1043.26 0 0.055
1 1 712.97 0 0.018 4.10 1 762.99 0 0.033
2 2 712.83 0 0.008 3.9 2 734.85 0 0.052
3 2 712.83 0 0.010 3.76 3 723.28 0 0.095
10 0 0 977.54 0 0.034 0.34 0 1043.26 0 0.049
1 1 717.97 0 0.009 3.03 1 767.99 0 0.031
2 1 717.97 0 0.010 4.24 2 744.85 0 0.061
3 1 717.97 0 0.006 3.94 3 738.28 0 0.014
20 0 0 977.54 0 0.039 0.42 0 1043.26 0 0.045
1 1 727.97 0 0.011 2.90 1 777.99 0 0.032
2 1 727.97 0 0.010 3.79 2 764.85 0 0.014
3 1 727.97 0 0.009 3.85 2 764.85 0 0.016
50 0 0 977.54 0 0.020 0.39 0 1043.26 0 0.043
1 1 757.97 0 0.011 3.04 1 807.99 0 0.015
2 1 757.97 0 0.008 3.85 1 807.99 0 0.014
3 1 757.97 0 0.009 3.61 1 807.99 0 0.020
C K Continuous Env. Discretized Env.
Proposed Optimal Algo. IP Solver Proposed Optimal Algo.
$\theta(p^*)$ $\tau(p^*)$ #RP RT (s) RT (s) $\theta(p^*)$ $\tau(p^*)$ #RP RT (s)
1 0 0 977.54 0 0.055 0.36 0 1043.26 0 0.078
1 1 708.97 0 0.055 3.34 1 758.99 0 0.051
2 2 704.83 0 0.042 4.38 2 726.85 0 0.086
3 3 703 0 0.009 4.04 3 711.28 0 0.034
5 0 0 977.54 0 0.041 0.48 0 1043.26 0 0.055
1 1 712.97 0 0.018 4.10 1 762.99 0 0.033
2 2 712.83 0 0.008 3.9 2 734.85 0 0.052
3 2 712.83 0 0.010 3.76 3 723.28 0 0.095
10 0 0 977.54 0 0.034 0.34 0 1043.26 0 0.049
1 1 717.97 0 0.009 3.03 1 767.99 0 0.031
2 1 717.97 0 0.010 4.24 2 744.85 0 0.061
3 1 717.97 0 0.006 3.94 3 738.28 0 0.014
20 0 0 977.54 0 0.039 0.42 0 1043.26 0 0.045
1 1 727.97 0 0.011 2.90 1 777.99 0 0.032
2 1 727.97 0 0.010 3.79 2 764.85 0 0.014
3 1 727.97 0 0.009 3.85 2 764.85 0 0.016
50 0 0 977.54 0 0.020 0.39 0 1043.26 0 0.043
1 1 757.97 0 0.011 3.04 1 807.99 0 0.015
2 1 757.97 0 0.008 3.85 1 807.99 0 0.014
3 1 757.97 0 0.009 3.61 1 807.99 0 0.020
Table 3.  Average results of 100 random COBRA-like obstacle fields for various $K$ values ($C=1$)
K Proposed Optimal Algorithm IP Solver Ant System Algorithm
$\theta(p^*)$ $\tau(p^*)$ #RP RT (s) RT (s) % Dev. RT (s)
1 0.96 115.01 29.4 15.217 166.95 7.24% 258.87
2 1.80 108.06 10.5 5.444 167.96 6.90% 262.03
3 2.56 105.32 1.7 0.972 138.02 3.41% 181.97
4 3.04 104.37 0.7 0.490 86.10 0.84% 77.88
5 3.26 104.22 0.6 0.345 67.23 0.08% 31.50
6 3.35 104.16 0.01 0.118 63.64 0.00% 8.03
7 3.36 104.15 0.00 0.088 47.48 0.00% 5.33
8 3.36 104.15 0.00 0.084 53.81 0.00% 5.32
9 3.36 104.15 0.00 0.085 51.16 0.00% 5.33
K Proposed Optimal Algorithm IP Solver Ant System Algorithm
$\theta(p^*)$ $\tau(p^*)$ #RP RT (s) RT (s) % Dev. RT (s)
1 0.96 115.01 29.4 15.217 166.95 7.24% 258.87
2 1.80 108.06 10.5 5.444 167.96 6.90% 262.03
3 2.56 105.32 1.7 0.972 138.02 3.41% 181.97
4 3.04 104.37 0.7 0.490 86.10 0.84% 77.88
5 3.26 104.22 0.6 0.345 67.23 0.08% 31.50
6 3.35 104.16 0.01 0.118 63.64 0.00% 8.03
7 3.36 104.15 0.00 0.088 47.48 0.00% 5.33
8 3.36 104.15 0.00 0.084 53.81 0.00% 5.32
9 3.36 104.15 0.00 0.085 51.16 0.00% 5.33
Table 4.  Average results of 100 random COBRA-like obstacle fields for various $C$ values ($K=2$)
C Proposed Optimal Algorithm IP Solver Ant System Algorithm
$\theta(p^*)$ $\tau(p^*)$ #RP RT (s) RT (s) % Dev. RT (s)
0.1 1.99 106.39 11.9 6.734 264.838 3.21% 1072.552
0.5 1.90 107.14 11.3 6.482 247.793 9.45% 678.499
1 1.80 108.06 10.5 5.444 228.303 6.90% 262.030
2 1.59 109.78 8.9 5.292 179.448 5.67% 128.304
5 1.24 113.94 4.7 3.139 117.311 1.62% 49.419
10 0.86 119.15 3.1 2.100 58.123 0.07% 23.278
20 0.46 125.81 0.0 0.076 35.616 0.00% 12.800
C Proposed Optimal Algorithm IP Solver Ant System Algorithm
$\theta(p^*)$ $\tau(p^*)$ #RP RT (s) RT (s) % Dev. RT (s)
0.1 1.99 106.39 11.9 6.734 264.838 3.21% 1072.552
0.5 1.90 107.14 11.3 6.482 247.793 9.45% 678.499
1 1.80 108.06 10.5 5.444 228.303 6.90% 262.030
2 1.59 109.78 8.9 5.292 179.448 5.67% 128.304
5 1.24 113.94 4.7 3.139 117.311 1.62% 49.419
10 0.86 119.15 3.1 2.100 58.123 0.07% 23.278
20 0.46 125.81 0.0 0.076 35.616 0.00% 12.800
Table 5.  Results of proposed optimal algorithm on 50 random COBRA-like obstacle fields for various $K$ values ($C=1$
K [10] × [10] [20] × [20] [50] × [50]
$\theta(p^*)$ $\tau(p^*)$ #RP RT (s) $\theta(p^*)$ $\tau(p^*)$ #RP RT (s) $\theta(p^*)$ $\tau(p^*)$ #RP RT (s)
1 0.88 173.70 45.6 0.027 0.54 157.68 4866.1 70.044 0.62 137.32 3800.0 546.432
2 1.84 161.31 134.7 0.086 1.50 138.83 3138.3 48.120 1.60 122.26 2800.0 409.321
3 2.78 147.07 300.7 0.455 2.50 127.72 1657.8 24.312 2.46 116.06 3189.2 192.275
4 3.76 134.59 158.4 0.164 3.64 119.29 504.9 8.294 3.16 113.31 4079.5 162.626
5 4.82 124.43 18.9 0.012 4.62 114.55 73.1 0.180 3.98 111.02 3416.2 139.945
6 5.28 119.65 7.3 0.007 5.32 113.01 66.4 0.118 4.54 110.51 3157.9 132.476
7 6.04 116.68 4.9 0.005 6.04 111.76 22.2 0.046 4.90 110.05 2616.8 104.004
8 6.48 114.57 7.6 0.007 6.76 110.96 29.3 0.055 5.56 109.65 1201.6 77.306
9 7.10 113.06 4.7 0.005 7.28 110.59 31.7 0.059 6.04 109.35 400.0 7.138
K [10] × [10] [20] × [20] [50] × [50]
$\theta(p^*)$ $\tau(p^*)$ #RP RT (s) $\theta(p^*)$ $\tau(p^*)$ #RP RT (s) $\theta(p^*)$ $\tau(p^*)$ #RP RT (s)
1 0.88 173.70 45.6 0.027 0.54 157.68 4866.1 70.044 0.62 137.32 3800.0 546.432
2 1.84 161.31 134.7 0.086 1.50 138.83 3138.3 48.120 1.60 122.26 2800.0 409.321
3 2.78 147.07 300.7 0.455 2.50 127.72 1657.8 24.312 2.46 116.06 3189.2 192.275
4 3.76 134.59 158.4 0.164 3.64 119.29 504.9 8.294 3.16 113.31 4079.5 162.626
5 4.82 124.43 18.9 0.012 4.62 114.55 73.1 0.180 3.98 111.02 3416.2 139.945
6 5.28 119.65 7.3 0.007 5.32 113.01 66.4 0.118 4.54 110.51 3157.9 132.476
7 6.04 116.68 4.9 0.005 6.04 111.76 22.2 0.046 4.90 110.05 2616.8 104.004
8 6.48 114.57 7.6 0.007 6.76 110.96 29.3 0.055 5.56 109.65 1201.6 77.306
9 7.10 113.06 4.7 0.005 7.28 110.59 31.7 0.059 6.04 109.35 400.0 7.138
[1]

Yi Gao, Rui Li, Yingjing Shi, Li Xiao. Design of path planning and tracking control of quadrotor. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021063

[2]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[3]

Sheng-I Chen, Yen-Che Tseng. A partitioning column approach for solving LED sorter manipulator path planning problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021055

[4]

Yongkun Wang, Fengshou He, Xiaobo Deng. Multi-aircraft cooperative path planning for maneuvering target detection. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021050

[5]

Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044

[6]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

[7]

Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045

[8]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521

[9]

Chonghu Guan, Xun Li, Rui Zhou, Wenxin Zhou. Free boundary problem for an optimal investment problem with a borrowing constraint. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021049

[10]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[11]

Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks & Heterogeneous Media, 2021, 16 (2) : 155-185. doi: 10.3934/nhm.2021003

[12]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2907-2946. doi: 10.3934/dcds.2020391

[13]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066

[14]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056

[15]

Grace Nnennaya Ogwo, Chinedu Izuchukwu, Oluwatosin Temitope Mewomo. A modified extragradient algorithm for a certain class of split pseudo-monotone variational inequality problem. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021011

[16]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[17]

Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, Guo-Wei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 67-97. doi: 10.3934/fods.2021006

[18]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037

[19]

Fabio Camilli, Serikbolsyn Duisembay, Qing Tang. Approximation of an optimal control problem for the time-fractional Fokker-Planck equation. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021013

[20]

Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20.

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (101)
  • HTML views (466)
  • Cited by (1)

Other articles
by authors

[Back to Top]