MULTIOBJECTIVE A-STAR

被引：129

作者：

STEWART, BS ^{[1
]}

WHITE, CC ^{[1
]}

机构：

[1] UNIV VIRGINIA, SCH ENGN & APPL SCI, DEPT SYST ENGN, CHARLOTTESVILLE, VA 22901 USA

来源：

JOURNAL OF THE ACM | 1991年 / 38卷 / 04期

关键词：

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