article

Free access

Multiobjective A*

Authors:

Bradley S. Stewart,

Chelsea C. White, IIIAuthors Info & Claims

Journal of the ACM (JACM), Volume 38, Issue 4

Pages 775 - 814

https://doi.org/10.1145/115234.115368

Published: 01 October 1991 Publication History

PDF eReader

References

[1]

AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. Data Structures and Algorithms. Addison-Wesley, Reading, Mass., 1983.

Crossref

Google Scholar

[2]

BEHZAD, M., CHARTRAND, G., AND LESNIAK-FOSTER, L. Graphs and Digraphs. Prlndle, Weber, and Schmidt, Boston, Mass., 1979.

Google Scholar

[3]

BELLMAN, R.E. Dynamic Programming. Princeton Univ. Press, Princeton, N.J., 1957.

Crossref

Google Scholar

[4]

BOGETOFT, P. General communication schemes for multiobjeetive decision making. Europ. J. Op. Res. 26 (1986), 108-122.

Google Scholar

[5]

BROCKHOFF, K. Experimental test of MCDM algorithms in a modular approach. Europ. J. Op. Res. 22 (1985), 159-166.

Google Scholar

[6]

CANGPU, W. Multi-criteria dynamic programming. Sci. Sinica 23 (July 1980), 814-822.

Google Scholar

[7]

CARRAWAY, R. L., MORIN, T. L., AND MOSKOWITZ, H. Generalized dynamic programming for multicriteria optimization. Europ. d. Op. Res. 44 (Jan. 1990), 95-104.

Google Scholar

[8]

DONALD, B.R. A search algorithm for motion planning with six degrees of freedom. Artif. Int. 31 (1987), 295-353.

Crossref

Google Scholar

[9]

HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.

Google Scholar

[10]

HART, P. E., NILSSON, N. J., AND RAPHAEL, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cvbern. SSC-4 (1968), 100-107.

Google Scholar

[11]

HART, P. E., NILSSON, N. J. AND RAPHAEL, B. "Correction to 'A formal basis for the heuristic determination of minimum cost paths.' "' SIGART Newsletter 37 (1972), 28-29.

Crossref

Google Scholar

[12]

HENIG, M. I. The principle of optimality in dynamic programming with returns in partially ordered sets. Math. Op. Res. 10 (Aug. 1985), 462-470.

Google Scholar

[13]

KEENEY, R. L. AND RAIFFA, H. Decisions with multiple objectives: Preferences and va&e tradeoffs. New York, 1976.

Google Scholar

[14]

KOK, M. The interface with deosion makers and some experimental results in interactive multiple objective programming methods. Europ. Y. Op. Res. 26 (1986), 96-107.

Google Scholar

[15]

}KOKSALAN, M., KARWAN, M. H., AND ZIONTS, S. Approaches for discrete alternative multiple criteria problems for different types of criteria. Working Paper No. 572, School of Management, SUNY Buffalo, Buffalo, N.Y., June 1983.

Google Scholar

[16]

KORHONEN, P J A hmrarchlcal lnteracnve method for ranking alternatlves with multiple qualitative criteria Europ. J. Op. Res. 24 (1986), 265-276.

Google Scholar

[17]

KORHONEN, P. J., MosKowrrz, H., ~,ND WALLENIUS, J. A progressive algorithm for modeling and solving multiple-criteria decision problems Op. Res. 34 (Sep-Oct. 1986), 726-731.

Crossref

Google Scholar

[18]

KWA, J. B H. On the consastency assumption, monotone criterion and the monotone restriction SIGART Newsletter 103 (Jan. 1988), 29-31.

Crossref

Google Scholar

[19]

LEWNE, P. AND POMEROL, J. PRIAM, and interactive program for choosing among mulnple attribute alternanves Europ. J. Op. Res. 25 (1986), 272-280.

Google Scholar

[20]

Liu, C.L. Introduction to Combinatorial Mathematics. McGraw-Hill, New York, 1968.

Google Scholar

[21]

MOND, B AND ROSINGER, E E. Interactive weight assessment in mulnple attribute declsaon making. Europ. J. Op. Res. 22 (1985) 19-25.

Google Scholar

[22]

NmSSON, N.J. Problem-Solving Methods in Arttficml Intelligence. McGraw-Hill, New York, 1971

Crossref

Google Scholar

[23]

NmSSON, N.J. Principles of Artificial lntelhgence. Morgan-Kaufmann, San Mateo, Cahf., 1980.

Crossref

Google Scholar

[24]

PEARL, J. Heuristics: Intelligent Search Strategies for Computer Problem Solvmg. Addison- Wesley, Reading, Mass., 1984.

Crossref

Google Scholar

[25]

SAWARAGI, Y., NAKAYAMA, H AND TANINO, T. Theorv of Multiobjecttve Optimization. Academic Press, Orlando, 1985

Google Scholar

[26]

STEWART, B.S. Heuristzc Search with a General Order Relation. Ph.D. Dassertanon. Umv. Virginia, Charlottesville, Va. Aug 1988.

Crossref

Google Scholar

[27]

TAR, JAN, R.A. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1983.

Crossref

Google Scholar

[28]

TUCKER, A. Apphed Combmatorics. 2nd ed. John Wiley & Sons, New York, 1984.

Crossref

Google Scholar

[29]

VANSNICK, J. On the problem of weights in mulnple criteria decision making the noncompensatory approach. Europ. J, Op. Res. 24 (1986), 288-294.

Google Scholar

[30]

WroTE, D.J. OptimahO, and Efficwncv. Wiley, New York, 1982.

Google Scholar

[31]

WnrrE, C. C IiI, SAGE, A. P, AND DOZONO, S. A model of multmttrlbute decls~onmaking and trade-off weight determination under uncertainty IEEE Trans. Svst. Man. and Cvber. SMC-14 (Mar./Apr 1984), 223-229

Google Scholar

[32]

WHITe, C C. III, STEWART, B. S. AND CARRAWAY, R. L. Multiobjecnve, preference-based search in acycllc OR-graphs. Europ. J. Op. Res. (1991), accepted t\)r publication.

Google Scholar

[33]

ZELENY, M Multiple Criteria Decision Making. McGraw-Hill, New York, 1982.

Google Scholar

Cited By

View all

Craveirinha JClímaco JGirão-Silva RPascoal M(2024)Multiobjective Path Problems and Algorithms in Telecommunication Network Design—Overview and TrendsAlgorithms10.3390/a1706022217:6(222)Online publication date: 22-May-2024
https://doi.org/10.3390/a17060222
Richter JKolvenbach HValsecchi GHutter M(2024)Multi-Objective Global Path Planning for Lunar Exploration With a Quadruped Robot2024 International Conference on Space Robotics (iSpaRo)10.1109/iSpaRo60631.2024.10688158(48-55)Online publication date: 24-Jun-2024
https://doi.org/10.1109/iSpaRo60631.2024.10688158
Cuchý MJakob MMrkos J(2024)Route and charging planning for electric vehicles: a multi-objective approachTransportation Letters10.1080/19427867.2024.2315359(1-21)Online publication date: 14-Apr-2024
https://doi.org/10.1080/19427867.2024.2315359
Show More Cited By

Recommendations

Evolutionary multiobjective optimization
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

Many optimization problems are multiobjective in nature in the sense that multiple, conflicting criteria need to be optimized simultaneously. Due to the conflict between objectives, usually, no single optimal solution exists. Instead, the optimum ...
Tutorial on Evolutionary Multiobjective Optimization
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Many optimization problems are multiobjective in nature in the sense that multiple, conflicting criteria need to be optimized simultaneously. Due to the conflict between objectives, usually, no single optimal solution exists. Instead, the optimum ...
A Multiobjective Differential Evolution Based on Decomposition for Multiobjective Optimization with Variable Linkages
Parallel Problem Solving from Nature - PPSN IX
Abstract
Although a number of multiobjective evolutionary algorithms have been proposed over the last two decades, not much effort has been made to deal with variable linkages in multiobjective optimization. Recently, we have suggested a general framework ...

Reviews

Reviewer: Don Goelman

The A* algorithm is a classical heuristic search procedure that is especially important to the artificial intelligence (AI) community. A* assumes a scalar metric for evaluating paths to its goal states, however, while many real-world problems involve multiple and even conflicting or unrelated objectives. Previous work in this area has concentrated largely on producing such scalar-valued metrics from the set of individual criteria for the different objectives. By contrast, the authors of this paper maintain a vector of objectives and the costs of reaching them. The goal of their algorithm, multiobjective A* (MOA*), is to find the set of nondominated alternatives . An alternative a is said to dominate an alternative b if a is at least as good as b with respect to all objectives and better with respect to at least one. Besides the opening and closing sections, this paper has three parts: an intuitive overview and trace of MOA*, a formal formulation of the problem and algorithm, and a section of formal proofs, in which the issues of termination, completeness, and admissibility are treated. This paper is therefore excellent for readers with a range of theoretical abilities and experience. The paper closes with a good bibliography, including many papers that have appeared in the European Journal of Operations Research .

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 38, Issue 4

Oct. 1991

272 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/115234

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1991

Published in JACM Volume 38, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

A* multiobjective decision making

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

164
Total Citations
View Citations
2,130
Total Downloads

Downloads (Last 12 months)184
Downloads (Last 6 weeks)19

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Craveirinha JClímaco JGirão-Silva RPascoal M(2024)Multiobjective Path Problems and Algorithms in Telecommunication Network Design—Overview and TrendsAlgorithms10.3390/a1706022217:6(222)Online publication date: 22-May-2024
https://doi.org/10.3390/a17060222
Richter JKolvenbach HValsecchi GHutter M(2024)Multi-Objective Global Path Planning for Lunar Exploration With a Quadruped Robot2024 International Conference on Space Robotics (iSpaRo)10.1109/iSpaRo60631.2024.10688158(48-55)Online publication date: 24-Jun-2024
https://doi.org/10.1109/iSpaRo60631.2024.10688158
Cuchý MJakob MMrkos J(2024)Route and charging planning for electric vehicles: a multi-objective approachTransportation Letters10.1080/19427867.2024.2315359(1-21)Online publication date: 14-Apr-2024
https://doi.org/10.1080/19427867.2024.2315359
Du HGuo ZZhang LCai Y(2024)Multi-Objective Loosely Synchronized Search for Multi-Objective Multi-Agent Path Finding with Asynchronous Actions基于多目标松散同步搜索的多目标多智能体异步路径规划Journal of Shanghai Jiaotong University (Science)10.1007/s12204-024-2744-x29:4(667-677)Online publication date: 24-Jun-2024
https://doi.org/10.1007/s12204-024-2744-x
Salzman OFelner AHernandez CZhang HChan SKoenig SElkind E(2023)Heuristic-search approaches for the multi-objective shortest-path problemProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/757(6759-6768)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/757
Hou YTao GZang ZKong GGong J(2023)Multi-Agent Path Finding for Non-Conflicting Paths: An Infinite Speed Conflict-Based Search Approach2023 42nd Chinese Control Conference (CCC)10.23919/CCC58697.2023.10241096(5500-5505)Online publication date: 24-Jul-2023
https://doi.org/10.23919/CCC58697.2023.10241096
Ren ZRubinstein ZSmith SRathinam SChoset H(2023)ERCA*: A New Approach for the Resource Constrained Shortest Path ProblemIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.329303924:12(14994-15005)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3293039
Kurbanov TCuchý MVokřínek J(2023)Fast One-to-Many Multicriteria Shortest Path SearchIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.328206924:10(10410-10419)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3282069
Ren ZRathinam SChoset H(2023)A Conflict-Based Search Framework for Multiobjective Multiagent Path FindingIEEE Transactions on Automation Science and Engineering10.1109/TASE.2022.318318320:2(1262-1274)Online publication date: Apr-2023
https://doi.org/10.1109/TASE.2022.3183183
Palmieri FPattipati KGennaro GBuonanno AFedele C(2023)Belief Propagation of Pareto Front in Multi-Objective MDP Graphs2023 IEEE 33rd International Workshop on Machine Learning for Signal Processing (MLSP)10.1109/MLSP55844.2023.10286009(1-6)Online publication date: 17-Sep-2023
https://doi.org/10.1109/MLSP55844.2023.10286009
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Evolutionary multiobjective optimization

Tutorial on Evolutionary Multiobjective Optimization

A Multiobjective Differential Evolution Based on Decomposition for Multiobjective Optimization with Variable Linkages

Reviews

Access critical reviews of Computing literature here