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

Larsen AKilic KLadefoged MSung I(2025)A novel path-finding approach for maritime search-and-rescue missions incorporating dynamic probability of a target locationEngineering Optimization10.1080/0305215X.2024.2446590(1-20)Online publication date: 6-Mar-2025
https://doi.org/10.1080/0305215X.2024.2446590
Ren ZHernández CLikhachev MFelner AKoenig SSalzman ORathinam SChoset H(2025)EMOA*: A framework for search-based multi-objective path planningArtificial Intelligence10.1016/j.artint.2024.104260339(104260)Online publication date: Feb-2025
https://doi.org/10.1016/j.artint.2024.104260
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
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 ...

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

168
Total Citations
View Citations
2,200
Total Downloads

Downloads (Last 12 months)207
Downloads (Last 6 weeks)31

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Larsen AKilic KLadefoged MSung I(2025)A novel path-finding approach for maritime search-and-rescue missions incorporating dynamic probability of a target locationEngineering Optimization10.1080/0305215X.2024.2446590(1-20)Online publication date: 6-Mar-2025
https://doi.org/10.1080/0305215X.2024.2446590
Ren ZHernández CLikhachev MFelner AKoenig SSalzman ORathinam SChoset H(2025)EMOA*: A framework for search-based multi-objective path planningArtificial Intelligence10.1016/j.artint.2024.104260339(104260)Online publication date: Feb-2025
https://doi.org/10.1016/j.artint.2024.104260
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
Skyler SShperberg SAtzmon DFelner ASalzman OChan SZhang HKeonig SYeoh WUlloa CLarson K(2024)Theoretical study on multi-objective heuristic searchProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/776(7021-7028)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/776
Ba BYu YWang RGotteland JGao Y(2024) A New Multiobjective A ∗ Algorithm With Time Window Applied to Large Airports Journal of Advanced Transportation10.1155/atr/75362172024:1Online publication date: 26-Nov-2024
https://doi.org/10.1155/atr/7536217
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
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