Gal A. Kaminka: Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Multilateral Matchmaking and Hybrid Coverage in Multi Agent Systems

Victor Shafran. Multilateral Matchmaking and Hybrid Coverage in Multi Agent Systems. Master's Thesis, Bar Ilan University,2008.

Download

[PDF]549.4kB  

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 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.

Additional Information

BibTeX

@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 Thu Feb 22, 2024 11:36:58