An optimal algorithm for the obstacle neutralization problem

Ali Fuat Alkaya; Dindar Oz

doi:10.3934/jimo.2016049

Article Contents

2017, Volume 13, Issue 2: 835-856. Doi: 10.3934/jimo.2016049

This issue Previous Article Robust design of sensor fusion problem in discrete time Next Article A memory gradient method based on the nonmonotone technique

An optimal algorithm for the obstacle neutralization problem

Ali Fuat Alkaya^1, and
Dindar Oz^2,

1.
Computer Engineering Department, Marmara University, Istanbul, 34722, Turkey
2.
Software Engineering Department, Yasar University, Izmir, 35100, Turkey

Received: March 31, 2015

Revised: November 30, 2015

Published: August 2017

Abstract Full Text(HTML) Figure(8) / Table(5) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 68U01, 49M25; Secondary: 97K30.

Citation:

Full Text(HTML)

Figure 1. An example to the obstacle neutralization problem and optimal paths for $K$ = 0, 1, 2 and 3

Download: Full-size image PowerPoint slide

Figure 2. PSA

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 4. Optimal Algorithm

Download: Full-size image PowerPoint slide

Figure 5. Details for creating a TAG

Download: Full-size image PowerPoint slide

Figure 6. An actual naval minefield data set, called the COBRA data

Download: Full-size image PowerPoint slide

Figure 7. An example depicting the solutions on continuous space and discretized space at three different resolution settings

Download: Full-size image PowerPoint slide

Figure 8. An example how there occurs many parallel paths on a discretized minefield

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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
K	$\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

| Show Table

DownLoad: CSV

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
C	$\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

| Show Table

DownLoad: CSV

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]
K	$\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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[2]	V. Aksakalli and E. Ceyhan, Optimal obstacle placement with disambiguations, Annals of Applied Statistics, 6 (2012), 1730-1774. doi: 10.1214/12-AOAS556.
[3]	V. Aksakalli, D. Fishkind, C. 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.
[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.
[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.
[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.
[7]	A. F. Alkaya, V. 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.
[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.
[9]	W. M. Carlyle, J. 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.
[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.
[11]	G. Dahl and B. Realfsen, Curve Approximation and Constrained Shortest Path Problems, International Symposium on Mathematical Programming (ISMP97), 1997.
[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.
[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.
[14]	D. E. Fishkind, C. E. Priebe, K. Giles, L. 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.
[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.
[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.
[17]	A. Jüittner, B. Szviatovski, I. 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.
[18]	T. Koch, Rapid Mathematical Prototyping, Ph. D. Thesis, Technische Universität Berlin, 2004.
[19]	F. Kuipers, T. Korkmaz, M. 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.
[20]	J. Latourell, B. 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.
[21]	S. H. K. Lee, Route Optimization Model for Strike Aircraft, Master's thesis, Naval Postgraduate School, Monterey, California, 1995.
[22]	P. C. Li, Planning the Optimal Transit for a Ship Through a Mapped Minefield, Master's thesis, Naval Postgraduate School, Monterey, California, 2009.
[23]	Y. M. Marghi, F. 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.
[24]	C. Mou, W. 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.
[25]	R. Muhandiramge, N. 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.
[26]	R. Nygaard, J. 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.
[27]	C. E. Priebe, D. E. Fishkind, L. 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.
[28]	C. E. Priebe, T. E. Olson and D. M. Healy Jr., Exploiting stochastic partitions for minefield detection, Proceedings of the SPIE, 3079 (1997), 508-518.
[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.
[30]	J. O. Royset, W. M. Carlyle and R. K. Wood, Routing military aircraft with a constrained shortest-path algorithm, Military Operations Research, 14 (2009), 31-52.
[31]	N. H. Witherspoon, J. H. Holloway, K. S. Davis, R. 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.
[32]	B. Yang, Y. Ding, Y. 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.
[33]	X. Ye, D. 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.
[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.
[35]	J. Y. Yen, Finding the k shortest loopless paths in a network, Management Science, 17 (1971), 712-716.
[36]	M. Zabarankin, S. Uryasev and R. Murphey, Aircraft routing under the risk of detection, Naval Research Logistics, 53 (2006), 728-747. doi: 10.1002/nav.20165.
[37]	M. Zabarankin, S. 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.
[38]	Q. Zhu, J. Hu, W. 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.