• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Victor Shafran. Multilateral Matchmaking and Hybrid Coverage in Multi Agent Systems. Master's Thesis, Bar Ilan University,2008.
This thesis has two parts. The first part presents a hybrid approach to the coverge problem under dead reckoning errors. Coverage is a canonical robotics task, where single or multiple robots are given a target work area, and move about the area until every point in the area is visited by the robots. There are many efficient exact-motion coverage algorithms, that cannot be used in practice, because they assume accurate movements by the robot; unfortunately, real robots have navigational errors---called dead reckoning errors. A standard costly solution is to utilize a hybrid approach where an exact-motion algorithm is used on a robot that continuously localizes, so as to make course corrections. We propose a novel hybrid coverage algorithm, called \sc Trim Sail. It takes as input an exact-movement algorithm, the coverage tool size, and a maximal dead-reckoning error bound. It optimizes use of the exact-movement algorithm, so as to execute its coverage plan while minimizing movement and localization costs. \sc Trim Sail guaranteescomplete coverage, even under dead-reckoning errors. We present several variants of\sc Trim Sail and demonstrate their efficacy in systematic experiments using data collected from real robots. We show that (i) the analytical predictions for execution costs match the actual performance of the robot; (ii) all versions outperform the standard hybrid; and (iii) \sc Trim Sail's performance is robust to errors in cost estimates.The second part discuss multilater matchmaking under time constraints. In open multiagent systems (MAS), agents need mechanisms to locate possible partners for joint activities. Matchmaking is the process of introducing two or more agents to one another. Many approaches to matchmaking use a centralized method, in which one or a few middle agents respond to matchmaking requests from all agents in the system. However, recent technology trends limit the efficacy of centralized systems. As a result we focus on distributed matchmaking, where each agent is capable of searching and announcing the activities it is seeking. Previous works on distributed matchmaking used techniques that are unidirectional in nature: One agent searches, while the other passively waits to be contacted. In contrast, we allow for multidirectional searches totake place, in which all potential partners are involved. We present a new distributed technique which scales well, and still maintains a relatively low matchmaking time and little communication overhead. In addition, our technique introduces very low storage and computational overhead for the agents. We empirically evaluate the proposed technique on bilateral matchmaking and show that it outperforms the existing techniques. Then, we further enhance our technique by using partial match queries for the case of multilateral (more than two partners) matchmaking and demonstrate its advantages.
@MastersThesis{victor-msc,
author = {Victor Shafran},
title = {Multilateral Matchmaking and Hybrid Coverage in Multi Agent Systems},
school = {{B}ar {I}lan {U}niversity},
year = {2008},
OPTkey = {},
OPTtype = {},
OPTaddress = {},
OPTmonth = {},
OPTnote = {},
OPTannote = {},
wwwnote = {},
abstract = { This thesis has two parts. The first part presents a hybrid approach to the coverge problem under dead reckoning errors. Coverage is a canonical robotics task, where single or multiple robots are given a target work area, and move about the area until every point in the area is visited by the robots. There are many efficient exact-motion coverage algorithms, that cannot be used in practice, because they assume accurate movements by the robot; unfortunately, real robots have navigational errors---called \emph{dead reckoning errors}. A standard costly solution is to utilize a hybrid approach where an exact-motion algorithm is used on a robot that continuously localizes, so as to make course corrections. We propose a novel hybrid coverage algorithm, called {\sc Trim Sail}. It takes as input an exact-movement algorithm, the coverage tool size, and a maximal dead-reckoning error bound. It optimizes use of the exact-movement algorithm, so as to execute its coverage plan while minimizing movement and localization costs. {\sc Trim Sail} guarantees
complete coverage, even under dead-reckoning errors. We present several variants of
{\sc Trim Sail} and demonstrate their efficacy in systematic experiments using data collected from real robots. We show that (i) the analytical predictions for execution costs match the actual performance of the robot; (ii) all versions outperform the standard hybrid; and (iii) {\sc Trim Sail}'s performance is robust to errors in cost estimates.
The second part discuss multilater matchmaking under time constraints. In open multiagent systems (MAS), agents need mechanisms to locate possible partners for
joint activities. Matchmaking is the process of introducing two or more agents to one another.
Many approaches to matchmaking use a centralized method, in which one or a few \emph{middle agents} respond to matchmaking requests from all agents in the system. However, recent technology trends limit the efficacy of centralized systems. As a result we focus on distributed matchmaking, where each
agent is capable of searching and announcing the activities it is seeking. Previous works on distributed matchmaking used techniques that are unidirectional in nature: One agent searches, while the other passively waits to be contacted. In contrast, we allow for multidirectional searches to
take place, in which all potential partners are involved. We present a new distributed technique which scales well, and still maintains a relatively low matchmaking time and little communication overhead. In addition, our technique introduces very low storage and computational overhead for the agents.
We empirically evaluate the proposed technique on bilateral matchmaking and show that it
outperforms the existing techniques. Then, we further enhance our technique by using partial
match queries for the case of multilateral (more than two partners) matchmaking and demonstrate its advantages.}
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Aug 30, 2024 17:29:51