A geometric approach to anytime constraint solving for TCSPs

Yeh Hong-Ming; Jane Yung Jen Hsu; Han Shen Huang

doi:10.1007/BFb0095284

A geometric approach to anytime constraint solving for TCSPs

Yeh Hong-Ming, Jane Yung Jen Hsu, Han Shen Huang

National Taiwan University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Temporal constraint satisfaction problems (TCSPs) are typically modelled as graphs or networks. Efficient algorithms are only available to find solutions for problems with limited topology. In this paper, we propose constraint geometry as an alternative approach to modeling TCSPs. Finding solutions to a TCSP is transformed into a search problem in the corresponding n-dimensional space. Violations of constriants can be measured in terms of spatial distances. As a result, approximate solutions can be identified when it is impossible or impractical to find exact solutions. A real-numbered evolutionary algorithm with special mutation operators has been designed to solve the general class of TCSPs. It can render approximate solutions at any time and improve the solution quality if given more time. Experiments on hundreds of randomly generated problems with representative parameters showed that the algorithm is more efficient and robust in comparison with the pathconsistency algorithm.

Original language	English
Title of host publication	PRICAI 1998
Subtitle of host publication	Topics in Artificial Intelligence - 5th Pacific Rim International Conference on Artificial Intelligence, Proceedings
Editors	Hing-Yan Lee, Hiroshi Motoda
Publisher	Springer Verlag
Pages	365-376
Number of pages	12
ISBN (Print)	354065271X, 9783540652717
DOIs	https://doi.org/10.1007/BFb0095284
State	Published - 1998
Externally published	Yes
Event	5th Pacific Rim Intemational Conference on Artificial Intelligence, PRICAI 1998 - Singapore, Singapore Duration: 22 11 1998 → 27 11 1998

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1531
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th Pacific Rim Intemational Conference on Artificial Intelligence, PRICAI 1998
Country/Territory	Singapore
City	Singapore
Period	22/11/98 → 27/11/98

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1998.

Access to Document

10.1007/BFb0095284

Cite this

Hong-Ming, Y., Hsu, J. Y. J., & Huang, H. S. (1998). A geometric approach to anytime constraint solving for TCSPs. In H.-Y. Lee, & H. Motoda (Eds.), PRICAI 1998: Topics in Artificial Intelligence - 5th Pacific Rim International Conference on Artificial Intelligence, Proceedings (pp. 365-376). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1531). Springer Verlag. https://doi.org/10.1007/BFb0095284

Hong-Ming, Yeh ; Hsu, Jane Yung Jen ; Huang, Han Shen. / A geometric approach to anytime constraint solving for TCSPs. PRICAI 1998: Topics in Artificial Intelligence - 5th Pacific Rim International Conference on Artificial Intelligence, Proceedings. editor / Hing-Yan Lee ; Hiroshi Motoda. Springer Verlag, 1998. pp. 365-376 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2f54281c5b4349f7b5996a22fe6bd40d,

title = "A geometric approach to anytime constraint solving for TCSPs",

abstract = "Temporal constraint satisfaction problems (TCSPs) are typically modelled as graphs or networks. Efficient algorithms are only available to find solutions for problems with limited topology. In this paper, we propose constraint geometry as an alternative approach to modeling TCSPs. Finding solutions to a TCSP is transformed into a search problem in the corresponding n-dimensional space. Violations of constriants can be measured in terms of spatial distances. As a result, approximate solutions can be identified when it is impossible or impractical to find exact solutions. A real-numbered evolutionary algorithm with special mutation operators has been designed to solve the general class of TCSPs. It can render approximate solutions at any time and improve the solution quality if given more time. Experiments on hundreds of randomly generated problems with representative parameters showed that the algorithm is more efficient and robust in comparison with the pathconsistency algorithm.",

author = "Yeh Hong-Ming and Hsu, \{Jane Yung Jen\} and Huang, \{Han Shen\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1998.; 5th Pacific Rim Intemational Conference on Artificial Intelligence, PRICAI 1998 ; Conference date: 22-11-1998 Through 27-11-1998",

year = "1998",

doi = "10.1007/BFb0095284",

language = "英语",

isbn = "354065271X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "365--376",

editor = "Hing-Yan Lee and Hiroshi Motoda",

booktitle = "PRICAI 1998",

address = "德国",

}

Hong-Ming, Y, Hsu, JYJ & Huang, HS 1998, A geometric approach to anytime constraint solving for TCSPs. in H-Y Lee & H Motoda (eds), PRICAI 1998: Topics in Artificial Intelligence - 5th Pacific Rim International Conference on Artificial Intelligence, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1531, Springer Verlag, pp. 365-376, 5th Pacific Rim Intemational Conference on Artificial Intelligence, PRICAI 1998, Singapore, Singapore, 22/11/98. https://doi.org/10.1007/BFb0095284

A geometric approach to anytime constraint solving for TCSPs. / Hong-Ming, Yeh; Hsu, Jane Yung Jen; Huang, Han Shen.
PRICAI 1998: Topics in Artificial Intelligence - 5th Pacific Rim International Conference on Artificial Intelligence, Proceedings. ed. / Hing-Yan Lee; Hiroshi Motoda. Springer Verlag, 1998. p. 365-376 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1531).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A geometric approach to anytime constraint solving for TCSPs

AU - Hong-Ming, Yeh

AU - Hsu, Jane Yung Jen

AU - Huang, Han Shen

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1998.

PY - 1998

Y1 - 1998

N2 - Temporal constraint satisfaction problems (TCSPs) are typically modelled as graphs or networks. Efficient algorithms are only available to find solutions for problems with limited topology. In this paper, we propose constraint geometry as an alternative approach to modeling TCSPs. Finding solutions to a TCSP is transformed into a search problem in the corresponding n-dimensional space. Violations of constriants can be measured in terms of spatial distances. As a result, approximate solutions can be identified when it is impossible or impractical to find exact solutions. A real-numbered evolutionary algorithm with special mutation operators has been designed to solve the general class of TCSPs. It can render approximate solutions at any time and improve the solution quality if given more time. Experiments on hundreds of randomly generated problems with representative parameters showed that the algorithm is more efficient and robust in comparison with the pathconsistency algorithm.

AB - Temporal constraint satisfaction problems (TCSPs) are typically modelled as graphs or networks. Efficient algorithms are only available to find solutions for problems with limited topology. In this paper, we propose constraint geometry as an alternative approach to modeling TCSPs. Finding solutions to a TCSP is transformed into a search problem in the corresponding n-dimensional space. Violations of constriants can be measured in terms of spatial distances. As a result, approximate solutions can be identified when it is impossible or impractical to find exact solutions. A real-numbered evolutionary algorithm with special mutation operators has been designed to solve the general class of TCSPs. It can render approximate solutions at any time and improve the solution quality if given more time. Experiments on hundreds of randomly generated problems with representative parameters showed that the algorithm is more efficient and robust in comparison with the pathconsistency algorithm.

UR - https://www.scopus.com/pages/publications/84958041281

U2 - 10.1007/BFb0095284

DO - 10.1007/BFb0095284

M3 - 会议稿件

AN - SCOPUS:84958041281

SN - 354065271X

SN - 9783540652717

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 365

EP - 376

BT - PRICAI 1998

A2 - Lee, Hing-Yan

A2 - Motoda, Hiroshi

PB - Springer Verlag

T2 - 5th Pacific Rim Intemational Conference on Artificial Intelligence, PRICAI 1998

Y2 - 22 November 1998 through 27 November 1998

ER -

Hong-Ming Y, Hsu JYJ, Huang HS. A geometric approach to anytime constraint solving for TCSPs. In Lee HY, Motoda H, editors, PRICAI 1998: Topics in Artificial Intelligence - 5th Pacific Rim International Conference on Artificial Intelligence, Proceedings. Springer Verlag. 1998. p. 365-376. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0095284

A geometric approach to anytime constraint solving for TCSPs

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this