HAL - INRIA :: [inria-00598712, version 1] Multi-Agent Electro-Location and the Among Constraint

inria-00598712, version 1

Multi-Agent Electro-Location and the Among Constraint

Gilles Chabert ( Auteur à contacter de préférence )^a^, 1, 2, Frédéric Boyer ()^a^, 3, Sophie Demassey ()^a^, 1, 4

N° RR-7640 (2011)

Résumé : In this paper, we give a new approach for the localization of several autonomous fish robots equipped with the electric sense. The approach is based on interval arithmetic and constraint programming. It introduces a generalization of the Among constraint which was used so far in the different context of resource allocation in logistics. We prove that the bound consistency for a conjunction of Among constraints with interval domains is NP-complete in the vector case and polynomial in the one-dimensional case. Although it was designed for electric fish robots, this work is not restricted to this type of systems. The approach can be easily extended to other multi-agent systems with low-range sensing.

a – Ecole des Mines de Nantes
1 : Laboratoire d'Informatique de Nantes Atlantique (LINA)
CNRS : UMR6241 – Université de Nantes – Ecole des Mines de Nantes
2 : TASC (INRIA - LINA)
INRIA – Ecole des Mines de Nantes – Université de Nantes – CNRS : UMR6241
3 : Institut de Recherche en Communications et en Cybernétique de Nantes (IRCCyN)
CNRS : UMR6597 – Université de Nantes – École Centrale de Nantes – Ecole des Mines de Nantes – Ecole Polytechnique de l'Université de Nantes
4 : Laboratoire Informatique d'Avignon (LIA)
Université d'Avignon

inria-00598712, version 1
http://hal.inria.fr/inria-00598712
oai:hal.inria.fr:inria-00598712
Contributeur : Gilles Chabert <>
Soumis le : Mardi 7 Juin 2011, 13:18:49
Dernière modification le : Vendredi 17 Juin 2011, 16:47:55

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

%F inria-00598712, version 1
%0 Report
%U http://hal.inria.fr/inria-00598712
%2 INFO:INFO_AI;INFO:INFO_RB;INFO:INFO_DM;INFO:INFO_MA;INFO:INFO_CC
%T Multi-Agent Electro-Location and the Among Constraint
%A Chabert, Gilles
%A Boyer, Frédéric
%A Demassey, Sophie
%+ Laboratoire d'Informatique de Nantes Atlantique - LINA , TASC - INRIA - LINA , Institut de Recherche en Communications et en Cybernétique de Nantes - IRCCyN , Laboratoire Informatique d'Avignon - LIA
%X In this paper, we give a new approach for the localization of several autonomous fish robots equipped with the electric sense. The approach is based on interval arithmetic and constraint programming. It introduces a generalization of the Among constraint which was used so far in the different context of resource allocation in logistics. We prove that the bound consistency for a conjunction of Among constraints with interval domains is NP-complete in the vector case and polynomial in the one-dimensional case. Although it was designed for electric fish robots, this work is not restricted to this type of systems. The approach can be easily extended to other multi-agent systems with low-range sensing.
%2 Cet article propose une nouvelle approche pour le problème de la localisation de robots autonomes sous-marins dotés du sens électrique. Basée sur l'arithmétique d'intervalles et la programmation par contraintes, elle considère une généralisation de la contrainte Among, jusqu'ici utilisée principalement dans un contexte logistique (allocation de ressources). Nous prouvons que le calcul de la cohérence aux bornes pour une conjonction de contraintes Among dont les domaines des valeurs forment des intervalles est NP-complet dans le cas général et polynomial en une dimension. Bien que ce travail ait été conduit pour des robots sous-marin éléctriques, son cadre d'application dépasse ce type de technologie. L'approche peut en effet être facilement étendue à d'autres systèmes multi-agents dont les capteurs sont à faible portée.
%G Anglais
%2 Rapport de recherche
%P 20
%8 2011-06-07
%Z RR-7640
%2 17803

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00598712"><monogr>
<author><persName><forename>Gilles</forename><surname>Chabert</surname></persName>
<affiliation>
<orgName type="laboratory">LINA</orgName>
<orgName type="team">Laboratoire d'Informatique de Nantes Atlantique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6241</orgName>
<orgName type="institution">Université de Nantes</orgName>
<orgName type="institution">Ecole des Mines de Nantes</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA - LINA</orgName>
<orgName type="team">TASC</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Ecole des Mines de Nantes</orgName>
<orgName type="institution">Université de Nantes</orgName>
<orgName type="institution">CNRS : UMR6241</orgName>
</affiliation>
</author>
<author><persName><forename>Frédéric</forename><surname>Boyer</surname></persName>
<affiliation>
<orgName type="laboratory">IRCCyN</orgName>
<orgName type="team">Institut de Recherche en Communications et en Cybernétique de Nantes</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6597</orgName>
<orgName type="institution">Université de Nantes</orgName>
<orgName type="institution">École Centrale de Nantes</orgName>
<orgName type="institution">Ecole des Mines de Nantes</orgName>
<orgName type="institution">Ecole Polytechnique de l'Université de Nantes</orgName>
</affiliation>
</author>
<author><persName><forename>Sophie</forename><surname>Demassey</surname></persName>
<affiliation>
<orgName type="laboratory">LINA</orgName>
<orgName type="team">Laboratoire d'Informatique de Nantes Atlantique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6241</orgName>
<orgName type="institution">Université de Nantes</orgName>
<orgName type="institution">Ecole des Mines de Nantes</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIA</orgName>
<orgName type="team">Laboratoire Informatique d'Avignon</orgName>
<country>FR</country>
<orgName type="institution">Université d'Avignon</orgName>
</affiliation>
</author>
<title type="main" level="m">Multi-Agent Electro-Location and the Among Constraint</title><title type="main" level="m">Multi-Agent Electro-Location and the Among Constraint</title><imprint><biblScope type="publicationDate">2011-06-07</biblScope><biblScope type="pp">20</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00598712</idno><idno type="HALFile">http://hal.inria.fr/inria-00598712/PDF/RR-7640.pdf</idno></biblStruct>
</listBibl>
</listBibl>