Dissertation
Decision Making for Teams of Mobile Robots
Zusammenfassung
In the past years, we could observe a significant amount of new robotic systems in science, industry, and everyday life. To reduce the complexity of these systems, the industry constructs robots that are designated for the execution of a specific task such as vacuum cleaning, autonomous driving, observation, or transportation operations. As a result, such robotic systems need to combine their capabilities to accomplish complex tasks that exceed the abilities of individual robots. However, to achieve emergent cooperative behavior, multi-robot systems require a decision process that copes with the communication challenges of the application domain. This work investigates a distributed multi-robot decision process, which addresses unreliable and transient communication. This process composed by five steps, which we embedded into the ALICA multi-agent coordination language guided by the PROViDE negotiation middleware. The first step encompasses the specification of the decision problem, which is an integral part of the ALICA implementation. In our decision process, we describe multi-robot problems by continuous nonlinear constraint satisfaction problems. The second step addresses the calculation of solution proposals for this problem specification. Here, we propose an efficient solution algorithm that integrates incomplete local search and interval propagation techniques into a satisfiability solver, which forms a satisfiability modulo theories (SMT) solver. In the third decision step, the PROViDE middleware replicates the solution proposals among the robots. This replication process is parameterized with a distribution method, which determines the consistency properties of the proposals. In a fourth step, we investigate the conflict resolution. Therefore, an acceptance method ensures that each robot supports one of the replicated proposals. As we integrated the conflict resolution into the replication process, a sound selection of the distribution and acceptance methods leads to an eventual convergence of the robot proposals. In order to avoid the execution of conflicting proposals, the last step comprises a decision method, which selects a proposal for implementation in case the conflict resolution fails. The evaluation of our work shows that the usage of incomplete solution techniques of the constraint satisfaction solver outperforms the runtime of other state-of-the-art approaches for many typical robotic problems. We further show by experimental setups and practical application in the RoboCup environment that our decision process is suitable for making quick decisions in the presence of packet loss and delay. Moreover, PROViDE requires less memory and bandwidth compared to other state-of-the-art middleware approaches.
Zitieren
@phdthesis{urn:nbn:de:hebis:34-2016110251246,
author={Witsch, Andreas},
title={Decision Making for Teams of Mobile Robots},
school={Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatik},
month={11},
year={2016}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2016$n2016 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2016110251246 3000 Witsch, Andreas 4000 Decision Making for Teams of Mobile Robots / Witsch, Andreas 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2016110251246=x R 4204 \$dDissertation 4170 5550 {{Informatik}} 5550 {{Robotik}} 5550 {{Verteiltes System}} 5550 {{Middleware}} 7136 ##0##urn:nbn:de:hebis:34-2016110251246
2016-11-02T08:19:06Z 2016-11-02T08:19:06Z 2016-11-02 urn:nbn:de:hebis:34-2016110251246 http://hdl.handle.net/123456789/2016110251246 eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Robotics Distributed Systems Decision Making Middleware Continous Nonlinear Constraint Satisfaction Problem Solving 004 Decision Making for Teams of Mobile Robots Dissertation In the past years, we could observe a significant amount of new robotic systems in science, industry, and everyday life. To reduce the complexity of these systems, the industry constructs robots that are designated for the execution of a specific task such as vacuum cleaning, autonomous driving, observation, or transportation operations. As a result, such robotic systems need to combine their capabilities to accomplish complex tasks that exceed the abilities of individual robots. However, to achieve emergent cooperative behavior, multi-robot systems require a decision process that copes with the communication challenges of the application domain. This work investigates a distributed multi-robot decision process, which addresses unreliable and transient communication. This process composed by five steps, which we embedded into the ALICA multi-agent coordination language guided by the PROViDE negotiation middleware. The first step encompasses the specification of the decision problem, which is an integral part of the ALICA implementation. In our decision process, we describe multi-robot problems by continuous nonlinear constraint satisfaction problems. The second step addresses the calculation of solution proposals for this problem specification. Here, we propose an efficient solution algorithm that integrates incomplete local search and interval propagation techniques into a satisfiability solver, which forms a satisfiability modulo theories (SMT) solver. In the third decision step, the PROViDE middleware replicates the solution proposals among the robots. This replication process is parameterized with a distribution method, which determines the consistency properties of the proposals. In a fourth step, we investigate the conflict resolution. Therefore, an acceptance method ensures that each robot supports one of the replicated proposals. As we integrated the conflict resolution into the replication process, a sound selection of the distribution and acceptance methods leads to an eventual convergence of the robot proposals. In order to avoid the execution of conflicting proposals, the last step comprises a decision method, which selects a proposal for implementation in case the conflict resolution fails. The evaluation of our work shows that the usage of incomplete solution techniques of the constraint satisfaction solver outperforms the runtime of other state-of-the-art approaches for many typical robotic problems. We further show by experimental setups and practical application in the RoboCup environment that our decision process is suitable for making quick decisions in the presence of packet loss and delay. Moreover, PROViDE requires less memory and bandwidth compared to other state-of-the-art middleware approaches. open access Witsch, Andreas Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatik Geihs, Kurt (Prof. Dr.) Freisleben, Bernd (Prof. Dr.-Ing. ) Zündorf, Albert (Prof. Dr.) Zipf, Peter (Prof. Dr.-Ing. ) Distributed algorithms Informatik Robotik Verteiltes System Middleware 2016-08-23
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden:
:Urheberrechtlich geschützt