Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Simulation-based Optimization and Decision Making with Imperfect Information
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
2011 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The purpose of this work is to provide simulation-based support for making optimal (or near-optimal) decisions in situations where decision makers are faced with imperfect information. We develop several novel techniques and algorithms for simulation-based optimization and decision support and apply them to two categories of problems: (i) Unmanned Aerial Vehicle (UAV) path planning in search operations, and; (ii) optimization of business process models. Common features of these two problems for which analytical approaches are not available, are the presence of imperfect information and their inherent complexity.

In the UAV path planning problem, the objective is to define the path of a UAV searching for a target on a known road network. It is assumed that the target is moving toward a goal and we have some uncertain information about the start point of the target, its velocity, and the final goal of the target. The target does not take evasive action to avoid being detected. The UAV is equipped with a sensor, which may detect the target once it is in the sensor’s scope. Nevertheless, the detection process is uncertain and the sensor is subject to both false-positive and false-negative errors. We propose three different solutions, two of which are simulation-based. The most promising solution is an on-line simulation-based method that estimates the location of the target by using a Sequential Monte Carlo (SMC) method. During the entire mission, different UAV paths are simulated and the one is chosen that most reduces the uncertainty about the location of the target.

In the optimization of the business process models, several different but related problems are addressed: (i) we define a measure of performance for a business process model based on the value added by agents (employees) to the process; (ii) we use this model for optimization of the business process models. Different types of processes are distinguished and methods for finding the optimal or near-optimal solutions are provided; (iii) we propose a model for estimating the performance of collaborative agents. This model is used to solve a class of Assignment Problems (AP), where tasks are assigned to collaborative agents; (iv) we propose a model for team activity and the performance of a team of agents. We introduce different collaboration strategies between agents and a negotiation algorithm for resolving conflicts between agents. We compare the effect of different strategies on the output of the team.

Most of the studied cases are complex problems for which no analytical solution is available. Simulation methods are successfully applied to these problems. They are shown to be more general than analytical models for handling uncertainty since they usually have fewer assumptions and impose no restrictions on the probability distributions involved. Our investigation confirms that simulation is a powerful tool for providing decision-making support. Moreover, our proposed algorithms and methods in the accompanying articles contribute to providing support for making optimal and in some cases near-optimal decisions: (i) our tests of the UAV simulation-based search methods on a simulator show that the on-line simulation method has generally a high performance and detects the target in a reasonable time. The performance of this method was compared with the detection time when the UAV had the exact information about the initial location of the target, its velocity, and its path (minimum detection time). This comparison indicated that the online simulation method in many cases achieved a near-optimal performance in the studied scenario; (ii) our business process optimization framework combines simulation with the Hungarian method and finds the optimal solution for all cases where the assignment of tasks does not change the workflow of the process. For the most general cases, where the assignment of tasks may change the workflow, we propose an algorithm that finds near-optimal solutions. In this algorithm, simulation, which deals with the uncertainty in the process, is combined with the Hungarian method and hill-climbing heuristics. In the study of assigning tasks to collaborative agents we suggest a Genetic Algorithm (GA) that finds near-optimal solutions with a high degree of accuracy, stability, scalability and robustness. While investigating the effect of different agent strategies on the output of a team, we find that the output of a team is near-optimal, when agents choose a collaboration strategy that follows the principle of least effort (Zipf’s law) and use our suggested algorithm for negotiation and resolving conflicts. 

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2011. , xiii, 36 p.
Series
Trita-ICT-ECS AVH, ISSN 1653-6363 ; 11:09
Keyword [en]
Simulation-based Optimization, UAV Path Planning, Business Process Optimization
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-50171ISBN: 978-91-7501-151-6 (print)OAI: oai:DiVA.org:kth-50171DiVA: diva2:461227
Public defence
2011-12-09, Sal D, Forum, Isafjordsgatan 39, Kista, 14:00 (English)
Opponent
Supervisors
Note
QC 20111202Available from: 2011-12-02 Created: 2011-12-02 Last updated: 2011-12-07Bibliographically approved
List of papers
1. Path planning for UAVs using symbiotic simulation
Open this publication in new window or tab >>Path planning for UAVs using symbiotic simulation
2006 (English)In: Modelling and Simulation 2006 / [ed] Nketsa, A; Paludetto, M; Bertelle, C, 2006, 207-213 p.Conference paper, Published paper (Refereed)
Abstract [en]

The problem of efficient path planning for Unmanned Aerial Vehicles (UAV) with a surveillance mission in a dynamic environment can in some cases be solved using Symbiotic Simulation (S2), i.e. an on-line simulation that interacts in real-time with the UAV and chooses its path. Sequential Monte Carlo Simulation, known also as Particle Filtering (PF) is an instance of such a simulation. In this paper we describe a methodology and an algorithm to use PF for efficient path planning of a UAV which searches a road network for a target. To verify whether this method is feasible and to supply a tool to compare different methods a simulator is developed. This simulator and its features are presented in this paper as well.

Keyword
modeling and simulation, particle filtering, path planning, symbiotic simulation, unmanned aerial vehicle (UAV)
National Category
Computer and Information Science
Identifiers
urn:nbn:se:kth:diva-42211 (URN)000245528900034 ()978-90-77381-30-4 (ISBN)
Conference
European Simulation and Modelling Conference (ESM 2006) Location: Toulouse, France, Date: OCT 23-25, 2006
Note
QC 20111010Available from: 2011-10-10 Created: 2011-10-06 Last updated: 2011-12-02Bibliographically approved
2. Simulation-aided path planning of UAV
Open this publication in new window or tab >>Simulation-aided path planning of UAV
2007 (English)In: Proceedings Of The 2007 Winter Simulation Conference: Vols 1-5, 2007, 1285-1293 p.Conference paper, Published paper (Refereed)
Abstract [en]

The problem of path planning for Unmanned Aerial Vehicles (UAV) with a tracking mission, when some a priori information about the targets and the environment is available can in some cases be addressed using simulation. Sequential Monte Carlo Simulation can be used to assess the state of the system and target when the UAV reaches the area of responsibility and during the tracking task. This assessment of the future is then used to compare the impact of choosing different alternative paths on the expected value of the detection time. A path with a lower expected value of detection time is preferred. In this paper the details of this method is described. Simulations are performed by a special purpose simulation tool to show the feasibility of this method and compare it with an exhaustive search.

National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-39651 (URN)10.1109/WSC.2007.4419737 (DOI)000256071800152 ()2-s2.0-49749105591 (Scopus ID)978-1-4244-1305-8 (ISBN)
Conference
2007 Winter Simulation Conference, WSC; Washington, DC; 9 December 2007 through 12 December 2007
Available from: 2011-09-12 Created: 2011-09-12 Last updated: 2011-12-02Bibliographically approved
3. Using on-line simulation for adaptive path planning of UAVs
Open this publication in new window or tab >>Using on-line simulation for adaptive path planning of UAVs
2007 (English)In: DS-RT 2007: 11TH IEEE INTERNATIONAL SYMPOSIUM ON DISTRIBUTED SIMULATION AND REAL-TIME APPLICATIONS, PROCEEDINGS / [ed] Roberts, DJ; Theodoropoulos, GK; ElSaddik, A, LOS ALAMITOS: IEEE COMPUTER SOC , 2007, 167-174 p.Conference paper, Published paper (Refereed)
Abstract [en]

In a surveillance mission, the task of Unmanned. Aerial Vehicles (UAV) path planning can in some cases be addressed using Sequential Monte Carlo (SMC) simulation. If sufficient a priori information about the target and the environment is available an assessment of the future state of the target is obtained by the SMC simulation. This assessment is used in a set of "what-if" simulations to compare different alternative UAV paths. In a static environment this simulation can be conducted prior to the mission. However if the environment is dynamic, it is required to run the "what-if" simulations on-line i.e. in real-time. In this paper the details of this on-line simulation approach in UAV path planning is studied and its performance is compared with two other methods: an off-line simulation aided path planning and an exhaustive search method. The conducted simulations indicate that the on-line simulation has generally a higher performance compared with the two other methods.

Place, publisher, year, edition, pages
LOS ALAMITOS: IEEE COMPUTER SOC, 2007
Series
IEEE/ACM International Symposium on Distributed Simulation and Real-Time Applications, ISSN 1550-6525
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-39462 (URN)000251799200021 ()2-s2.0-46449106347 (Scopus ID)978-0-7695-3011-6 (ISBN)
Conference
11th IEEE International Symposium on Distributed Simulation and Real-Time Applications. Chania, GREECE. OCT 22-24, 2007
Available from: 2011-09-09 Created: 2011-09-09 Last updated: 2011-12-02Bibliographically approved
4. Estimating performance of a business process model
Open this publication in new window or tab >>Estimating performance of a business process model
2009 (English)In: Winter Simulation Conference, 2009, 2828-2839 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we suggest a model for estimating performance of human organizations and business processes. This model is based on subjective assessment of the capabilities of the available human resources, the importance of these capabilities, and the influence of the peripheral factors on the resources. The model can be used to compare different resource allocation schemes in order to choose the most beneficial one. We suggest an extension to Business Process Modeling Notation (BPMN) by including performance measure of performers and the probability by which an outgoing Sequence Flow from a Gateway is chosen. We also propose an analytical method for estimating the overall performance of BPMN in simple cases and a simulation method, which can be used for more complicated scenarios. To illustrate how these methods work, we apply them to part of a military Operational Planning Process and discuss the results.

Series
Winter Simulation Conference Proceedings, ISSN 0891-7736
National Category
Computer and Information Science
Identifiers
urn:nbn:se:kth:diva-34234 (URN)10.1109/WSC.2009.5429226 (DOI)000289492501134 ()2-s2.0-77951564263 (Scopus ID)978-1-4244-5770-0 (ISBN)
Conference
2009 Winter Simulation Conference, WSC 2009; Austin, TX; 13 December 2009 through 16 December 2009
Note
QC 20110614Available from: 2011-06-14 Created: 2011-05-30 Last updated: 2011-12-02Bibliographically approved
5. A framework for simulation-based optimization of business process models
Open this publication in new window or tab >>A framework for simulation-based optimization of business process models
2012 (English)In: Simulation (San Diego, Calif.), ISSN 0037-5497, E-ISSN 1741-3133, Vol. 88, no 7, 852-869 p.Article in journal (Refereed) Published
Abstract [en]

The Assignment Problem is a classical problem in the field of combinatorial optimization, having a wide range of applications in a variety of contexts. In general terms, the Assignment Problem consists of determining the best assignment of tasks to agents according to a predefined objective function. Different variants of the Assignment Problem have been extensively investigated in the literature in the last 50 years. In this work, we introduce and analyze the problem of optimizing a business process model with the objective of finding the most beneficial assignment of tasks to agents. Despite similarities, this problem is distinguished from the traditional Assignment Problem in that we consider tasks to be part of a business process model, being interconnected according to defined rules and constraints. In other words, assigning a business process to agents is a more complex form of the Assignment Problem. Two main categories of business processes, assignment-independent and assignment-dependent, are distinguished. In the first category, different assignments of tasks to agents do not affect the flow of the business process, while processes in the second category contain critical tasks that may change the workflow, depending on who performs them. In each category several types of processes are studied. Algorithms for finding optimal and near-optimal solutions to these categories are presented. For the first category, depending on the type of process, the Hungarian algorithm is combined with either the analytical method or simulation to provide an optimal solution. For the second category, we introduce two algorithms. The first one finds an optimal solution, but is feasible only when the number of critical tasks is small. The second algorithm is applicable to large number of critical tasks, but provides a near-optimal solution. In the second algorithm a hill-climbing heuristic method is combined with the Hungarian algorithm and simulation to find an overall near-optimal solution. A series of tests is conducted which demonstrates that the proposed algorithms efficiently find optimal solutions for assignment-independent and near-optimal solutions for assignment-dependent processes.

Place, publisher, year, edition, pages
Sage Publications, 2012
Keyword
Simulation-based Optimization, Business Process Optimization, Assignment Problem, Hungarian Algorithm
National Category
Computer Systems
Identifiers
urn:nbn:se:kth:diva-50160 (URN)10.1177/0037549711417880 (DOI)000305969800006 ()2-s2.0-84863533910 (Scopus ID)
Note

QC 20120731

Available from: 2011-12-02 Created: 2011-12-02 Last updated: 2017-12-08Bibliographically approved
6. Optimization of Task Assignment to Collaborating Agents
Open this publication in new window or tab >>Optimization of Task Assignment to Collaborating Agents
2011 (English)In: IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011, Paris, France: IEEE Computational Intelligence Society , 2011, 17-24 p.Conference paper, Published paper (Refereed)
Abstract [en]

The classic task assignment problem (AP) assigns m agents to n tasks, where each task is assigned to exactly one agent. This problem and many of its variations, including the case where a task is assigned to a group of agents working independently, have been discussed extensively in the literature. We consider a specific class of task assignment problems where each task is assigned to a group of collaborating agents that work as a team. Thus, changing one of the group members may have a vital impact on the output of the group. We assume that each agent has a set of capabilities and each task has certain requirements. The objective is to assign agents to teams such that the gain is maximized.

We suggest a Genetic Algorithm (GA) for finding a near optimal solution to this class of task assignment problems. To the best of our knowledge, this class of APs has not been considered in the literature, probably due to the difficulty of evaluating the performance of a team of agents. Recently, we have developed a formal method for measuring performance of a team which is used in this paper to formulate the objective function of our GA. We analyze the quality of the obtained solution by comparing the result of our GA with (a) the exact solution of some smaller problems, and (b) with the results of the exact solution of specific cases that can be obtained by the Hungarian algorithm. We provide experimental results on efficiency, stability, robustness and scalability of the solution obtained by our GA.

Place, publisher, year, edition, pages
Paris, France: IEEE Computational Intelligence Society, 2011
Keyword
Task Assignment Problem, Genetic Algorithms, Evolutionary Algorithms, Optimization
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-45938 (URN)10.1109/SCIS.2011.5976547 (DOI)2-s2.0-80052082446 (Scopus ID)978-161284196-0 (ISBN)
Conference
IEEE Symposium on Computational Intelligence in Scheduling. Paris, 11 April 2011 - 15 April 2011
Note

QC 20111102

Available from: 2011-11-01 Created: 2011-11-01 Last updated: 2014-03-28Bibliographically approved
7. A Model for Estimating the Performance of a Team of Agents
Open this publication in new window or tab >>A Model for Estimating the Performance of a Team of Agents
2011 (English)In: Proceedings of the 2011 IEEE International Conference on Systems, Man and Cybernetics (SMC 2011), IEEE Press, 2011, 2393-2400 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we present a model for estimatingthe performance of a team of agents, based on the capabilities of the agents and importance of these capabilities for the task. Performance of a team is assumed to be the sum of contributions of individual agents and contributions of subgroups built in the team. We introduce a set of notations, which is required for discussing the suggested models. We also propose a model to estimate the benefit of an agent from interaction with other agents in a subgroup. Based on this benefit model and different (common) strategies, the agents devise plans in which they formulate to what extent they are willing to cooperate with other agents. A negotiation algorithm that resolves the conflicts between the desires of the agents is presented. The effect of this algorithm and different strategies are tested on a set of generated data. The test results show that the performance of a team when the agents choose a cooperation strategy that follows the principle of least effort (Zipf’s law) is higher than teams with other cooperation strategies.

Place, publisher, year, edition, pages
IEEE Press, 2011
Series
IEEE International Conference on Systems Man and Cybernetics Conference Proceedings, ISSN 1062-922X
Keyword
Business, Indexes, Schedules, Stochastic processes, Symmetric matrices, Teamwork, Vectors
National Category
Computer Systems
Identifiers
urn:nbn:se:kth:diva-49919 (URN)10.1109/ICSMC.2011.6084036 (DOI)000298615102118 ()2-s2.0-83755185915 (Scopus ID)978-1-4577-0652-3 (ISBN)
Conference
International Conference on Systems, Man and Cybernetics (SMC 2011)
Note
© 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.Available from: 2011-12-02 Created: 2011-11-30 Last updated: 2012-04-03Bibliographically approved

Open Access in DiVA

fulltext(318 kB)629 downloads
File information
File name FULLTEXT01.pdfFile size 318 kBChecksum SHA-512
e0b202ddded94317fff27df2cfe8124c12c75b72b68e5b17644276c7f7a2f0bfe2d23b5edfb7f971d06b1b013f69936770240f933b575387e4ff7ae7c8e48c02
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Kamrani, Farzad
By organisation
Software and Computer Systems, SCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 629 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 673 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf