Solving the Multi Observer 3D Visual Area Coverage Scheduling Problem by Decomposition
ABSTRACT
This paper presents two solution methodologies for the Visual Area Coverage Scheduling problem. The objective is to schedule a number of dynamic observers over a given 3D terrain such that the total visual area covered (viewed) over a planning horizon is maximal. This problem is a more complicated extension of the Set Covering Problem, known to be Np-Hard. We present two decomposition based heuristic methods each containing three stages. The first methodology finds a set of area covering points, and then partitions them into routes (cover first, partition second). The second methodology partitions the area into a region for each observer, and then finds the best covering points and routes (partition first, cover second). In each, a last stage determines dwell (view) times so as to maximize the visible coverage smoothly over the terrain. Comparative tests were made for the two methods on real terrains for several scenarios. When comparing the best solutions of both methods the CF-PS method was slightly better. However, because of the increased computation time we suggest that the PF-CS method with a fine terrain approximation be used. This method is faster as partitioning the terrain into separate regions for each observer results in smaller coverage and routing problems. A sensitivity analysis of the number of observation points to the total number of terrain points covered depicted the classical notion of decreasing returns to scale, increasing in a convex manner as the number of observation points was increased. The best method achieved 100 percent coverage of the terrain by using only 2.7 percent of its points as observation points. Experts stated that the computer based solutions can save precious time and help plan observation missions with satisfying results.
This paper presents two solution methodologies for the Visual Area Coverage Scheduling problem. The objective is to schedule a number of dynamic observers over a given 3D terrain such that the total visual area covered (viewed) over a planning horizon is maximal. This problem is a more complicated extension of the Set Covering Problem, known to be Np-Hard. We present two decomposition based heuristic methods each containing three stages. The first methodology finds a set of area covering points, and then partitions them into routes (cover first, partition second). The second methodology partitions the area into a region for each observer, and then finds the best covering points and routes (partition first, cover second). In each, a last stage determines dwell (view) times so as to maximize the visible coverage smoothly over the terrain. Comparative tests were made for the two methods on real terrains for several scenarios. When comparing the best solutions of both methods the CF-PS method was slightly better. However, because of the increased computation time we suggest that the PF-CS method with a fine terrain approximation be used. This method is faster as partitioning the terrain into separate regions for each observer results in smaller coverage and routing problems. A sensitivity analysis of the number of observation points to the total number of terrain points covered depicted the classical notion of decreasing returns to scale, increasing in a convex manner as the number of observation points was increased. The best method achieved 100 percent coverage of the terrain by using only 2.7 percent of its points as observation points. Experts stated that the computer based solutions can save precious time and help plan observation missions with satisfying results.
Cite this paper
nullH. Stern, M. Zofi and M. Kaspi, "Solving the Multi Observer 3D Visual Area Coverage Scheduling Problem by Decomposition," American Journal of Operations Research, Vol. 1 No. 3, 2011, pp. 118-133. doi: 10.4236/ajor.2011.13014.
nullH. Stern, M. Zofi and M. Kaspi, "Solving the Multi Observer 3D Visual Area Coverage Scheduling Problem by Decomposition," American Journal of Operations Research, Vol. 1 No. 3, 2011, pp. 118-133. doi: 10.4236/ajor.2011.13014.
References
[1] J. O’Rourke, “Art Gallery Theorems and Algorithms,” Oxford University Press, Oxford, 1987. [2] S. Rana, “Two Approximate Solutions to the Art Gallery Problem,” Proceedings of 31st International Conference on Computer Graphics and Interactive Techniques (SIGRAPH), Los Angeles, 8-12 August 2004. [3] H. Stern, Y. Chassidim and M. Zofi, “Multiagent Visual Area Coverage Using a New Genetic Algorithm Selection Scheme,” European Journal of Operational Research, Vol. 175, No. 3, 2006, pp. 1890-1907. doi:10.1016/j.ejor.2005.02.078 [4] H. Stern, Y. Chassidim, M. Zofi and M. Kaspi, “Multi Agent Visual Area Coverage Strategies Using an Adaptive Queen Genetic Algorithm,” Proceedings of IASTED International Conference on Artificial Intelligence and Applications, Innsbruck, 14-16 February 2005. [5] W. R. Franklyn, “Applications of Analytical Cartography,” Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton, 2000. [6] M. Marengoni, B. A. Draper, A. Hanson and R. Sitaraman, “Placing Observers to Cover a Polyhedral Terrain in Polynomial Time,” Proceedings of the 3rd IEEE Workshop on Applications of Computer Vision, Sarasota, 2-4 December 1996, pp. 1-6. [7] V. V. Vazirani, “Approximation Algorithms,” Springer- Verlag, Berlin, 2001. [8] M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman and Co, San Francisco, 1979. [9] H. E. Gindy and D. Avis, “A Linear Algorithm for Computing the Visibility Polygon from a Point,” Journal of Algorithms, Vol. 2, No. 2, 1981, pp. 186-197. doi:10.1016/0196-6774(81)90019-5 [10] D. Cohen-Or and A. Shaked, “Visibility and Dead-Zones in Digital Terrain Maps,” Computer Graphics Forum, Vol. 14, No. 3, 1995, pp. 171-180. doi:10.1111/j.1467-8659.1995.cgf143_0171.x [11] F. M. Jonsson, “An Optimal Pathfinder for Vehicles in Real-World Digital Terrain Maps,” The Royal Institute of Science, School of Engineering Physics, Stockholm, 1997. [12] E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan and D. B. Shmoys, “The Traveling Salesman Problem,” John Wiley & Sons, Hoboken, 1992. [13] A. Jaszkiewicz, “Comparative Study of Multiple-Objective Metaheuristics on the Bi-Objective Set Covering Problem and the Pareto Memetic Algorithm,” Research Report, Institute of Computing Science, Poznan University of Technology, Poznań, 2001. [14] M. Garland and P. S. Heckbert, “Fast Triangular Approximation of Terrains and Height Fields,” Proceedings of SIGGRAPH’97 Conference, Los Angeles, 3-8 August 1997. [15] B. Hayes, “The Easiest Hard Problem,” American Scientist, Vol. 90, No. 2, 2002, pp. 113-117. doi:10.1511/2002.2.113
[1] J. O’Rourke, “Art Gallery Theorems and Algorithms,” Oxford University Press, Oxford, 1987. [2] S. Rana, “Two Approximate Solutions to the Art Gallery Problem,” Proceedings of 31st International Conference on Computer Graphics and Interactive Techniques (SIGRAPH), Los Angeles, 8-12 August 2004. [3] H. Stern, Y. Chassidim and M. Zofi, “Multiagent Visual Area Coverage Using a New Genetic Algorithm Selection Scheme,” European Journal of Operational Research, Vol. 175, No. 3, 2006, pp. 1890-1907. doi:10.1016/j.ejor.2005.02.078 [4] H. Stern, Y. Chassidim, M. Zofi and M. Kaspi, “Multi Agent Visual Area Coverage Strategies Using an Adaptive Queen Genetic Algorithm,” Proceedings of IASTED International Conference on Artificial Intelligence and Applications, Innsbruck, 14-16 February 2005. [5] W. R. Franklyn, “Applications of Analytical Cartography,” Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton, 2000. [6] M. Marengoni, B. A. Draper, A. Hanson and R. Sitaraman, “Placing Observers to Cover a Polyhedral Terrain in Polynomial Time,” Proceedings of the 3rd IEEE Workshop on Applications of Computer Vision, Sarasota, 2-4 December 1996, pp. 1-6. [7] V. V. Vazirani, “Approximation Algorithms,” Springer- Verlag, Berlin, 2001. [8] M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman and Co, San Francisco, 1979. [9] H. E. Gindy and D. Avis, “A Linear Algorithm for Computing the Visibility Polygon from a Point,” Journal of Algorithms, Vol. 2, No. 2, 1981, pp. 186-197. doi:10.1016/0196-6774(81)90019-5 [10] D. Cohen-Or and A. Shaked, “Visibility and Dead-Zones in Digital Terrain Maps,” Computer Graphics Forum, Vol. 14, No. 3, 1995, pp. 171-180. doi:10.1111/j.1467-8659.1995.cgf143_0171.x [11] F. M. Jonsson, “An Optimal Pathfinder for Vehicles in Real-World Digital Terrain Maps,” The Royal Institute of Science, School of Engineering Physics, Stockholm, 1997. [12] E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan and D. B. Shmoys, “The Traveling Salesman Problem,” John Wiley & Sons, Hoboken, 1992. [13] A. Jaszkiewicz, “Comparative Study of Multiple-Objective Metaheuristics on the Bi-Objective Set Covering Problem and the Pareto Memetic Algorithm,” Research Report, Institute of Computing Science, Poznan University of Technology, Poznań, 2001. [14] M. Garland and P. S. Heckbert, “Fast Triangular Approximation of Terrains and Height Fields,” Proceedings of SIGGRAPH’97 Conference, Los Angeles, 3-8 August 1997. [15] B. Hayes, “The Easiest Hard Problem,” American Scientist, Vol. 90, No. 2, 2002, pp. 113-117. doi:10.1511/2002.2.113