| 1. |
- Blikstad, Mathias, et al.
(författare)
-
A constraint generation procedure for pre-runtime scheduling of integrated modular avionic systems
- 2017
-
Ingår i: Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems.
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network.While the avionic systems are growing more and more complex, so is the challenge of scheduling them. Scheduling of the system has an important role in the development of new avionic systems since functionality typically is added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, in case this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one.In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20 000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within reasonable time.
|
|
| 2. |
- Blikstad, Mathias, et al.
(författare)
-
An Optimisation Approach for Pre-Runtime Scheduling of Tasks and Communication in an Integrated Modular Avionic System
- 2017
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network.While the avionic systems are growing more and more complex, so is the challenge of scheduling them. Scheduling of the system has an important role in the development of new avionic systems since functionality typically is added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, in case this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one.In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20 000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within reasonable time.
|
|
| 3. |
- Blikstad, Mathias, et al.
(författare)
-
An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system
- 2018
-
Ingår i: Optimization and Engineering. - : Springer Science and Business Media LLC. - 1389-4420 .- 1573-2924. ; 19:4, s. 977-1004
-
Tidskriftsartikel (refereegranskat)abstract
- In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network. While avionic systems are growing more and more complex, so is the challenge of scheduling them. The scheduling of the system has an important role in the development of new avionic systems, since functionality is typically added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, if this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one. In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for the scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20,000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within a reasonable time.
|
|
| 4. |
- Jonsson, Anders, et al.
(författare)
-
Limitations of acyclic causal graphs for planning
- 2014
-
Ingår i: Artificial Intelligence. - : Elsevier. - 0004-3702 .- 1872-7921. ; 210, s. 36-55
-
Tidskriftsartikel (refereegranskat)abstract
- Causal graphs are widely used in planning to capture the internal structure of planning instances. Researchers have paid special attention to the subclass of planning instances with acyclic causal graphs, which in the past have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. This naturally raises the question of whether planning is easier when the causal graph is acyclic. In this article we show that the answer to this question is no, proving that in the worst case, the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to STRIPS planning with negative preconditions. We show that the reduction still holds if we restrict actions to have at most two preconditions. Having established that planning is hard for acyclic causal graphs, we study two subclasses of planning instances with acyclic causal graphs. One such subclass is described by propositional variables that are either irreversible or symmetrically reversible. Another subclass is described by variables with strongly connected domain transition graphs. In both cases, plan existence is bounded away from PSPACE, but in the latter case, the problem of bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.
|
|
| 5. |
- Jonsson, Anders, et al.
(författare)
-
When Acyclicity is not Enough: Limitations of the Causal Graph
- 2013
-
Ingår i: Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. - : AAAI Press. - 9781577356097 ; , s. 117-125
-
Konferensbidrag (refereegranskat)abstract
- Causal graphs are widely used in planning to capture the internal structure of planning instances. In the past, causal graphs have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. It is generally believed that planning is easier when the causal graph is acyclic. In this paper we show that this is not true in the worst case, proving that the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to STRIPS planning with negative pre-conditions. Having established that planning is hard for acyclic causal graphs, we study a subclass of planning instances with acyclic causal graphs whose variables have strongly connected domain transition graphs. For this class, we show that plan existence is easy, but that bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.
|
|
| 6. |
- Jonsson, Peter, et al.
(författare)
-
Computational complexity of linear constraints over the integers
- 2013
-
Ingår i: Artificial Intelligence. - : Elsevier. - 0004-3702 .- 1872-7921. ; 195, s. 44-62
-
Tidskriftsartikel (refereegranskat)abstract
- Temporal reasoning problems arise in many areas of Al, including planning, natural language understanding, and reasoning about physical systems. The computational complexity of continuous-time temporal constraint reasoning is fairly well understood. There are, however, many different cases where discrete time must be considered; various scheduling problems and reasoning about sampled physical systems are two examples. Here, the complexity of temporal reasoning is not as well-studied nor as well-understood. In order to get a better understanding, we consider the powerful Horn disjunctive linear relations (Horn DLR) formalism adapted for discrete time and study its computational complexity. We show that the full formalism is NP-hard and identify several maximal tractable subclasses. We also lift the maximality results to obtain hardness results for other families of constraints. Finally, we discuss how the results and techniques presented in this paper can be used for studying even more expressive classes of temporal constraints.
|
|
| 7. |
- Jonsson, Peter, 1969-, et al.
(författare)
-
Discrete-Time Temporal Reasoning with Horn DLRs
- 2011
-
Ingår i: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. - : AAAI Press. - 9781577355168 ; , s. 931-936
-
Konferensbidrag (refereegranskat)abstract
- Temporal reasoning problems arise in many areas of AI, including planning, natural language understanding, and reasoning about physical systems. The computational complexity of continuous-time temporal constraint reasoning is fairly well understood. There are, however, many different cases where discrete time must be considered; various scheduling problems and reasoning about sampled physical systems are two examples. Here, the complexity of temporal reasoning is not as well-studied nor as well-understood. In order to get a better understanding, we consider the powerful Horn DLR formalism adapted for discrete time and study its computational complexity. We show that the full formalism is NP-hard and identify several maximal tractable subclasses. We also ‘lift’ the maximality results to obtain hardness results for other families of constraints. Finally, we discuss how the results and techniques presented in this paper can be used for studying even more expressive classes of temporal constraints
|
|
| 8. |
- Poletti Lundström, Tomas, 1986-
(författare)
-
Trons försvarare : Idéer om religion i svensk radikalnationalism 1988–2020
- 2022
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This dissertation outlines continuity and change in Swedish radical nationalism – a political ideology predominantly focused on connecting an imagined people with a distinct territory. The study focuses on how religion has been understood within the landscape of Swedish radical nationalism between 1988 and 2020. The landscape is termed radical-nationalist since its central articulation is nationalism. It is radical because of its actors’ urge to return nationalism to its roots, without compromising with other political ideologies, and because it is seen as a radical solution to the problems of national degeneration. The Swedish radical-nationalist landscape consists of ideological formations that are culture-oriented, race-oriented, and identity-oriented. These formations animate the actors moving across the landscape. Three such actors are analyzed in the dissertation, each having its own history and distinct position in relation to the ideological formations: the political party Sweden Democrats, the national socialist organization Nordic Resistance Movement, and the online influencer The Golden One. The study builds on a theoretical shift, usually labeled critical religion theory, which departs from religion as an analytical category to instead focus on the various definitions of, and ideas about, religion among the actors themselves. Religion is analyzed as a political concept within Swedish radical nationalism. The terminology of political concepts is borrowed from the theory of ideological morphology, where such concepts are located on an axis between center and periphery of a political ideology, from core concepts via adjacent concepts to peripheral concepts. In Swedish radical nationalism, the concept of religion is a demarcation against them, external enemies as well as internal traitors. Religion functions as an essential exclusionary mechanism aimed at imagined Others who are assumed to, in varying degrees, be superstitious, conspiratorial, fanatical, or divisive. However, the concept of religion also construes us, an imagined people, through ideas of a shared collective unconscious and a Volksgeist that via paganism and Christianity travels from a distant, and often forgotten, past. In conclusion, religion is recurrently one of the adjacent concepts that temporarily stabilizes the core of Swedish radical nationalism: people and territory. Like other concepts that are adjacent to the core – such as culture, race, and identity – the concept of religion stipulates who belongs to the people and the territory, and who should be excluded, disadvantaged, or eliminated.
|
|
