Routing and Scheduling in Answer Set Programming applied to Multi-Agent Path Finding: Preliminary Report
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909140086947840 |
|---|---|
| author | Kaminski, Roland Schaub, Torsten Son, Tran Cao Švancara, Jiří Wanko, Philipp |
| author_facet | Kaminski, Roland Schaub, Torsten Son, Tran Cao Švancara, Jiří Wanko, Philipp |
| contents | We present alternative approaches to routing and scheduling in Answer Set Programming (ASP), and explore them in the context of Multi-agent Path Finding. The idea is to capture the flow of time in terms of partial orders rather than time steps attached to actions and fluents. This also abolishes the need for fixed upper bounds on the length of plans. The trade-off for this avoidance is that (parts of) temporal trajectories must be acyclic, since multiple occurrences of the same action or fluent cannot be distinguished anymore. While this approach provides an interesting alternative for modeling routing, it is without alternative for scheduling since fine-grained timings cannot be represented in ASP in a feasible way. This is different for partial orders that can be efficiently handled by external means such as acyclicity and difference constraints. We formally elaborate upon this idea and present several resulting ASP encodings. Finally, we demonstrate their effectiveness via an empirical analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12153 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Routing and Scheduling in Answer Set Programming applied to Multi-Agent Path Finding: Preliminary Report Kaminski, Roland Schaub, Torsten Son, Tran Cao Švancara, Jiří Wanko, Philipp Artificial Intelligence Logic in Computer Science Symbolic Computation We present alternative approaches to routing and scheduling in Answer Set Programming (ASP), and explore them in the context of Multi-agent Path Finding. The idea is to capture the flow of time in terms of partial orders rather than time steps attached to actions and fluents. This also abolishes the need for fixed upper bounds on the length of plans. The trade-off for this avoidance is that (parts of) temporal trajectories must be acyclic, since multiple occurrences of the same action or fluent cannot be distinguished anymore. While this approach provides an interesting alternative for modeling routing, it is without alternative for scheduling since fine-grained timings cannot be represented in ASP in a feasible way. This is different for partial orders that can be efficiently handled by external means such as acyclicity and difference constraints. We formally elaborate upon this idea and present several resulting ASP encodings. Finally, we demonstrate their effectiveness via an empirical analysis. |
| title | Routing and Scheduling in Answer Set Programming applied to Multi-Agent Path Finding: Preliminary Report |
| topic | Artificial Intelligence Logic in Computer Science Symbolic Computation |
| url | https://arxiv.org/abs/2403.12153 |