MULTIOBJECTIVE A-STAR

被引:129
作者
STEWART, BS [1 ]
WHITE, CC [1 ]
机构
[1] UNIV VIRGINIA, SCH ENGN & APPL SCI, DEPT SYST ENGN, CHARLOTTESVILLE, VA 22901 USA
关键词
ALGORITHMS; THEORY; A-STAR MULTIOBJECTIVE DECISION-MAKING;
D O I
10.1145/115234.115368
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
A multiobjective generalization of the heuristic search algorithm A* is presented, called MOA*. The research is motivated by the observation that most real-world problems involve multiple, conflicting, and noncommensurate objectives. MOA* explicitly accommodates this observation by identifying the set of all nondominated paths from a specified start node to a given set of goal nodes in an OR graph. It is shown that MOA* is complete and, when used with a suitably defined set of admissible heuristic functions, admissible. Several results concerning the comparison of versions of MOA* directed by different sets of heuristic functions are provided. The implications of using a monotone or consistent set of heuristic functions in MOA* are discussed. Two simple examples are used to illustrate the behavior of the algorithm.
引用
收藏
页码:775 / 814
页数:40
相关论文
共 33 条