Genetic algorithms for positioning and utilizing sensors in synthetically generated landscapes

ABSTRACT

Positioning multiple sensors for acquisition of a a given environment is one of the fundamental research areas in various fields, such as military scouting, computer vision and robotics. In this paper, we propose a framework for locating an configuring a set of given sensors in a synthetically generated terrain with multiple objectives of maximization of visibility of the terrain, maximization of stealth of the sensors and minimization of cost of the sensors. Because of their utility-independent nature, these complementary and conflicting objectives are represented by a multiplicative global utility function based on multi-attribute utility theory. In addition to theoretic foundations, we also present how a Genetic Algorithms can be applied to maximize the global utility function for a given terrain.

REFERENCES

• 1: John Butler , Douglas J. Morrice , Peter W. Mullarkey, A Multiple Attribute Utility Theory Approach to Ranking and Selection, Management Science, v.47 n.6, p.800-816, June 2001 [doi>10.1287/mnsc.47.6.800.9812]
• 2: Tolga Can, Veysi Isler, and Ziya Ipekkan. Sensor optimization in a virtual environment. In 9th Conference on Computer Generated Forces and Behavioral Representation, Orlando, Florida, 2000.
• 3: Robert T. Clemen. Making Hard Decision. PWS Kent Publishing, Boston, MA, 1991.
• 4: Diane J. Cook , Piotr Gmytrasiewicz , Lawrence B. Holder, Decision-Theoretic Cooperative Sensor Planning, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.10, p.1013-1023, October 1996 [doi>10.1109/34.541410 ]
• 5: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics (2nd ed. in C): principles and practice, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 6: N. K. Jaiswal. Military Operations Research: Quantitative Decision Making. Kluwer Academic Publishers, Boston, MA, 1997.
• 7: R. L. Keeney and H. Raiffa. Decision with Multiple Objectives. John Wiley and Sons, New York, 1976.
• 8: Steen Kristensen. Sensor Planning with Bayesian Decision Theory. Robotics and Autonomous Systems, 19:273--286, 1997.
• 9: Lyudmila Mihaylova , Tine Lefebvre , Herman Bruyninckx , Klaas Gadeyne , Joris De Schutter, A Comparison of Decision Making Criteria and Optimization Methods for Active Robotic Sensing, Revised Papers from the 5th International Conference on Numerical Methods and Applications, p.316-324, August 20-24, 2002
• 10: Michael K. Reed , Peter K. Allen, Constraint-Based Sensor Planning for Scene Modeling, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1460-1467, December 2000 [doi>10.1109/34.895979 ]
• 11: John Spletzer and Camillo Taylor. Sensor planning and control in a dynamic environment. In Proceedings of International Conference on Robotics and Automation, 2002.
• 12: I. Stamos , P. K. Allen, Interactive Sensor Planning, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.489, June 23-25, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Military

General Terms:
Algorithms, Experimentation

Keywords:
genetic algorithms, sensor optimization, utility theory