| 1. |
- Aghighi, Meysam, 1988-, et al.
(författare)
-
A Multi-parameter Complexity Analysis of Cost-optimal and Net-benefit Planning
- 2016
-
Ingår i: Twenty-Sixth International Conference on Automated Planning and Scheduling King's College, London June 12, 2016 – June 17, 2016. - : AAAI Press. - 9781577357575 ; , s. 2-10
-
Konferensbidrag (refereegranskat)abstract
- Aghighi and Bäckström have previously studied cost-optimal planning (COP) and net-benefit planning (NBP) for three action cost domains: the positive integers (Z_+), the non-negative integers (Z_0) and the positive rationals (Q_+). These were indistinguishable under standard complexity analysis for both problems, but separated for COP using parameterised complexity analysis. With the plan cost, k, as parameter, COP was W[2]-complete for Z_+, but para-NP-hard for both Z_0 and Q_+, i.e. presumably much harder. NBP was para-NP-hard for all three domains, thus remaining unseparable. We continue by considering combinations with several additional parameters and also the non-negative rationals (Q_0). Examples of new parameters are the plan length, l, and the largest denominator of the action costs, d. Our findings include: (1) COP remains W[2]-hard for all domains, even if combining all parameters; (2) COP for Z_0 is in W[2] for the combined parameter {k,l}; (3) COP for Q_+ is in W[2] for {k,d} and (4) COP for Q_0 is in W[2] for {k,d,l}. For NBP we consider further additional parameters, where the most crucial one for reducing complexity is the sum of variable utilities. Our results help to understand the previous results, eg. the separation between Z_+ and Q_+ for COP, and to refine the previous connections with empirical findings.
|
|
| 2. |
- Aghighi, Meysam, et al.
(författare)
-
Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis
- 2016
-
Ingår i: ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE. - : IOS Press. - 9781614996712 - 9781614996729 ; , s. 184-192
-
Konferensbidrag (refereegranskat)abstract
- Cost-optimal planning has become a very well-studied topic within planning. Needless to say, cost-optimal planning has proven to be computationally hard both theoretically and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it from an approximation point of view. Even though such studies may be valuable in themselves, additional motivation is provided by the fact that there is a very close link between approximability and the performance of heuristics used in heuristic search. The aim of this paper is to analyse approximability (and indirectly the performance of heuristics) with respect to lower time bounds. That is, we are not content by merely classifying problems into complexity classes - we also study their time complexity. This is achieved by replacing standard complexity-theoretic assumptions (such as P not equal NP) with the exponential time hypothesis (ETH). This enables us to analyse, for instance, the performance of the h(+) heuristic and obtain general trade-off results that correlate approximability bounds with bounds on time complexity.
|
|
| 3. |
- Aghighi, Meysam, 1988-
(författare)
-
Computational Complexity of some Optimization Problems in Planning
- 2017
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Automated planning is known to be computationally hard in the general case. Propositional planning is PSPACE-complete and first-order planning is undecidable. One method for analyzing the computational complexity of planning is to study restricted subsets of planning instances, with the aim of differentiating instances with varying complexity. We use this methodology for studying the computational complexity of planning. Finding new tractable (i.e. polynomial-time solvable) problems has been a particularly important goal for researchers in the area. The reason behind this is not only to differentiate between easy and hard planning instances, but also to use polynomial-time solvable instances in order to construct better heuristic functions and improve planners. We identify a new class of tractable cost-optimal planning instances by restricting the causal graph. We study the computational complexity of oversubscription planning (such as the net-benefit problem) under various restrictions and reveal strong connections with classical planning. Inspired by this, we present a method for compiling oversubscription planning problems into the ordinary plan existence problem. We further study the parameterized complexity of cost-optimal and net-benefit planning under the same restrictions and show that the choice of numeric domain for the action costs has a great impact on the parameterized complexity. We finally consider the parameterized complexity of certain problems related to partial-order planning. In some applications, less restricted plans than total-order plans are needed. Therefore, a partial-order plan is being used instead. When dealing with partial-order plans, one important question is how to achieve optimal partial order plans, i.e. having the highest degree of freedom according to some notion of flexibility. We study several optimization problems for partial-order plans, such as finding a minimum deordering or reordering, and finding the minimum parallel execution length.
|
|
| 4. |
- Aghighi, Meysam, 1988-, et al.
(författare)
-
Cost-optimal and Net-benefit Planning : A Parameterised Complexity View
- 2015
-
Ingår i: 24th International Joint Conference on Artificial Intelligence (IJCAI-15). - : IJCAI-INT JOINT CONF ARTIF INTELL, ALBERT-LUDWIGS UNIV FREIBURG GEORGES-KOHLER-ALLEE, INST INFORMATIK, GEB 052, FREIBURG, D-79110, GERMANY. - 9781577357384 ; , s. 1487-1493
-
Konferensbidrag (refereegranskat)abstract
- Cost-optimal planning (COP) uses action costs and asks for a minimum-cost plan. It is sometimes assumed that there is no harm in using actions with zero cost or rational cost. Classical complexity analysis does not contradict this assumption; planning is PSPACE-complete regardless of whether action costs are positive or non-negative, integer or rational. We thus apply parameterised complexity analysis to shed more light on this issue. Our main results are the following. COP is W[2]-complete for positive integer costs, i.e. it is no harder than finding a minimum-length plan, but it is para-NPhard if the costs are non-negative integers or positive rationals. This is a very strong indication that the latter cases are substantially harder. Net-benefit planning (NBP) additionally assigns goal utilities and asks for a plan with maximum difference between its utility and its cost. NBP is para-NP-hard even when action costs and utilities are positive integers, suggesting that it is harder than COP. In addition, we also analyse a large number of subclasses, using both the PUBS restrictions and restricting the number of preconditions and effects.
|
|
| 5. |
- Aghighi, Meysam, 1988-, et al.
(författare)
-
Plan Reordering and Parallel Execution -- A Parameterized Complexity View
- 2017
-
Konferensbidrag (refereegranskat)abstract
- Bäckström has previously studied a number of optimization problems for partial-order plans, like finding a minimum deordering (MCD) or reordering (MCR), and finding the minimum parallel execution length (PPL), which are all NP-complete. We revisit these problems, but applying parameterized complexity analysis rather than standard complexity analysis. We consider various parameters, including both the original and desired size of the plan order, as well as its width and height. Our findings include that MCD and MCR are W[2]-hard and in W[P] when parameterized with the desired order size, and MCD is fixed-parameter tractable (fpt) when parameterized with the original order size. Problem PPL is fpt if parameterized with the size of the non-concurrency relation, but para-NP-hard in most other cases. We also consider this problem when the number (k) of agents, or processors, is restricted, finding that this number is a crucial parameter; this problem is fixed-parameter tractable with the order size, the parallel execution length and k as parameter, but para-NP-hard without k as parameter.
|
|
| 6. |
- Aghighi, Meysam, et al.
(författare)
-
Refining complexity analyses in planning by exploiting the exponential time hypothesis
- 2016
-
Ingår i: Annals of Mathematics and Artificial Intelligence. - : SPRINGER. - 1012-2443 .- 1573-7470. ; 78:2, s. 157-175
-
Tidskriftsartikel (refereegranskat)abstract
- The use of computational complexity in planning, and in AI in general, has always been a disputed topic. A major problem with ordinary worst-case analyses is that they do not provide any quantitative information: they do not tell us much about the running time of concrete algorithms, nor do they tell us much about the running time of optimal algorithms. We address problems like this by presenting results based on the exponential time hypothesis (ETH), which is a widely accepted hypothesis concerning the time complexity of 3-SAT. By using this approach, we provide, for instance, almost matching upper and lower bounds onthe time complexity of propositional planning.
|
|
| 7. |
- Andersson, Christer, et al.
(författare)
-
Acute intermittent porphyria in women : clinical expression, use and experience of exogenous sex hormones. A population-based study in northern Sweden
- 2003
-
Ingår i: Journal of Internal Medicine. - : Wiley. - 0954-6820 .- 1365-2796. ; 254:2, s. 176-183
-
Tidskriftsartikel (refereegranskat)abstract
- OBJECTIVE: To describe the clinical expression of acute intermittent porphyria (AIP) in women, their use of exogenous sex hormones, and the effects on AIP. DESIGN: A retrospective population-based study. SUBJECTS: All women aged > or =18 years (n = 190) with DNA-diagnosed AIP in northern Sweden. RESULTS: A total of 166 women (87%) participated; 91 (55%) had manifest AIP. Severe attacks were reported by 82%; 39% reported recurrent premenstrual AIP attacks and 22% reported chronic AIP symptoms. Oral hormonal contraceptives had been used by 58% of all these women and by 50 with manifest AIP (57%). Twelve women (24%) associated oral contraceptives as precipitating AIP attacks; in nine cases their first attack. One woman experienced relief from AIP symptoms. On commencing their treatment, 72% of the women with manifest AIP had not yet suffered their first attack. Twenty-two women (25%) aged > or =45 years had used hormonal replacement therapy (HRT) at menopause to remedy climacteric symptoms (the percutaneous route was most frequently used); no AIP attack was precipitated. HRT to remedy vaginal dryness was used by 26 women (28%) aged > or =45 years without triggering an AIP attack. Miscarriages were more frequent in women with manifest AIP (50%) than in the latent group (30%, P = 0.014). CONCLUSIONS: About half of the women with AIP had used oral hormonal contraceptives. As 25% of women with manifest AIP reported attacks associated with such drugs, caution must still be recommended. Menopausal HRT only rarely affected the disorder. Miscarriage was more common amongst women with manifest AIP.
|
|
| 8. |
- Andersson, Christer, 1945-, et al.
(författare)
-
Atypical attack of acute intermittent porphyria : paresis but not abdominal pain
- 2002
-
Ingår i: Journal of Internal Medicine. - : Wiley. - 0954-6820 .- 1365-2796. ; 252:3, s. 265-270
-
Tidskriftsartikel (refereegranskat)abstract
- We report a case of acute intermittent porphyria (AIP) in a 45-year-old woman. Her first attack occurred at the age of 38. Because of escalating cyclical premenstrual attacks, the following 2 years, depletion of the endogenous sex hormone was considered as haeme arginate treatment proved insufficient. Gonadotropin releasing hormone agonist treatment with low-dose oestradiol add back was quite successful initially but was abandoned after 18 months when progesterone add back precipitated a severe attack. Following hysterectomy and oophorectomy at age 42 and oestradiol add back, a remarkable monthly regularity of attacks ensured periodically but with milder symptoms. Two years after surgery, preceded by six attack-free months, a puzzling symptom-shift occurred, from abdominal pain, back and thigh pain during the attacks, to solely severe distal extensor paresis in the arms. Haeme arginate treatment interrupted the progress of the paresis almost immediately and motor function improved considerably up to the 9-month follow-up. Electrophysiological examination revealed only motor neuropathy, consistent with axonal degeneration. Subsequently the symptoms changed yet again, to sensory disturbances with numbness and dysesthesia as the primary expression followed by rather mild abdominal pain. However, cyclical attacks occurred, despite absence of endogenous ovarial hormone production, possibly attributable to impaired oestrogen metabolism in the liver, or adrenal oestrogen production. Treatment comprising oophorectomy, low-dose oestradiol add back and haeme arginate infusion for 2 days on the appearance of early AIP symptoms is now quite successful affording improvement in life quality.
|
|
| 9. |
- Bjursten, Henrik, et al.
(författare)
-
S100beta after coronary artery surgery: release pattern, source of contamination, and relation to neuropsychological outcome
- 1999
-
Ingår i: Annals of Thoracic Surgery. - 1552-6259. ; 68:6, s. 2202-2208
-
Tidskriftsartikel (refereegranskat)abstract
- BACKGROUND: S100beta has been suggested as a marker of brain damage after cardiac operation. The aim of this study was to characterize the early S100beta release in detail and relate it to neuropsychological outcome. METHODS: Three groups of patients were investigated. All patients underwent coronary artery bypass surgery (CABG) with extracorporeal circulation. In group A, 110 patients had sampling of S100beta for the first 10 postoperative hours and also underwent neuropsychological testing. In group B, 14 patients were examined for the effect of autotransfusion on S100beta levels. Eight patients in group C had their intraoperative bleeding processed with a cell-saving device. RESULTS: Group A had a heterogeneous release pattern with several rapid elevations in S100beta concentration. In group B, high concentrations of S100beta were found in the autotransfusion blood (range 0.2 to 210 microg/L) with a concurrent elevation of serum S100beta levels after transfusion of shed blood. In group C, high levels of S100beta were found in the blood from the surgical field (12.0+/-6.0 microg/L) and decreased (1.1+/-0.64 microg/L) after wash. Group C had significantly lower S100beta values at the end of cardiopulmonary bypass compared to group A (0.53+/-0.35 microg/L versus 2.40+/-1.5 microg/L). S100beta values were corrected for extracerebral contamination with a kinetic model. With this correction, an association was found between adverse neuropsychological outcome and S100beta release in group A (r = 0.39, p < 0.02). CONCLUSIONS: A significant amount of S100beta is found both in the blood from the surgical field and in the shed mediastinal blood postoperatively. Infusion of this blood will result in infusion of S100beta into the blood and interfere in the interpretation of early systemic S100beta values.
|
|
| 10. |
- Bäckström, Christer, et al.
(författare)
-
A complete parameterized complexity analysis of bounded planning
- 2015
-
Ingår i: Journal of computer and system sciences (Print). - : Elsevier. - 0022-0000 .- 1090-2724. ; 81:7, s. 1311-1332
-
Tidskriftsartikel (refereegranskat)abstract
- The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter "length of the solution plan." We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Backstrom and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not. (C) 2015 Elsevier Inc. All rights reserved.
|
|
