Using the Cross-Entropy Method to Guide/Govern Mobile Agent’s Path Finding in Networks
Identifieur interne : 003036 ( Istex/Curation ); précédent : 003035; suivant : 003037Using the Cross-Entropy Method to Guide/Govern Mobile Agent’s Path Finding in Networks
Auteurs : Bjarne E. Helvik [Norvège] ; Otto Wittner [Norvège]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2001.
Abstract
Abstract: The problem of finding paths in networks is general and many faceted with a wide range of engineering applications in communication networks. Finding the optimal path or combination of paths usually leads to NP-hard combinatorial optimization problems. A recent and promising method, the cross-entropy method proposed by Rubinstein, manages to produce optimal solutions to such problems in polynomial time. However this algorithm is centralized and batch oriented. In this paper we show how the cross-entropy method can be reformulated to govern the behaviour of multiple mobile agents which act independently and asynchronously of each other. The new algorithm is evaluate on a set of well known Travelling Salesman Problems. A simulator, based on the Network Simulator package, has been implemented which provide realistic simulation environments. Results show good performance and stable convergence towards near optimal solution of the problems tested.
Url:
DOI: 10.1007/3-540-44651-6_24
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003036
Links to Exploration step
ISTEX:8AAF70A4EEDC5E11808518960B53DC10CE2D1CC1Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Using the Cross-Entropy Method to Guide/Govern Mobile Agent’s Path Finding in Networks</title><author><name sortKey="Helvik, Bjarne E" sort="Helvik, Bjarne E" uniqKey="Helvik B" first="Bjarne E." last="Helvik">Bjarne E. Helvik</name><affiliation wicri:level="1"><mods:affiliation>Department of Telematics, Norwegian University of Science and Technology, Norway</mods:affiliation><country xml:lang="fr">Norvège</country><wicri:regionArea>Department of Telematics, Norwegian University of Science and Technology</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: bjarne@item.ntnu.no</mods:affiliation><country wicri:rule="url">Norvège</country></affiliation></author><author><name sortKey="Wittner, Otto" sort="Wittner, Otto" uniqKey="Wittner O" first="Otto" last="Wittner">Otto Wittner</name><affiliation wicri:level="1"><mods:affiliation>Department of Telematics, Norwegian University of Science and Technology, Norway</mods:affiliation><country xml:lang="fr">Norvège</country><wicri:regionArea>Department of Telematics, Norwegian University of Science and Technology</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: wittner@item.ntnu.no</mods:affiliation><country wicri:rule="url">Norvège</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:8AAF70A4EEDC5E11808518960B53DC10CE2D1CC1</idno><date when="2001" year="2001">2001</date><idno type="doi">10.1007/3-540-44651-6_24</idno><idno type="url">https://api.istex.fr/document/8AAF70A4EEDC5E11808518960B53DC10CE2D1CC1/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">003036</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003036</idno><idno type="wicri:Area/Istex/Curation">003036</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Using the Cross-Entropy Method to Guide/Govern Mobile Agent’s Path Finding in Networks</title><author><name sortKey="Helvik, Bjarne E" sort="Helvik, Bjarne E" uniqKey="Helvik B" first="Bjarne E." last="Helvik">Bjarne E. Helvik</name><affiliation wicri:level="1"><mods:affiliation>Department of Telematics, Norwegian University of Science and Technology, Norway</mods:affiliation><country xml:lang="fr">Norvège</country><wicri:regionArea>Department of Telematics, Norwegian University of Science and Technology</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: bjarne@item.ntnu.no</mods:affiliation><country wicri:rule="url">Norvège</country></affiliation></author><author><name sortKey="Wittner, Otto" sort="Wittner, Otto" uniqKey="Wittner O" first="Otto" last="Wittner">Otto Wittner</name><affiliation wicri:level="1"><mods:affiliation>Department of Telematics, Norwegian University of Science and Technology, Norway</mods:affiliation><country xml:lang="fr">Norvège</country><wicri:regionArea>Department of Telematics, Norwegian University of Science and Technology</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: wittner@item.ntnu.no</mods:affiliation><country wicri:rule="url">Norvège</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2001</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">8AAF70A4EEDC5E11808518960B53DC10CE2D1CC1</idno><idno type="DOI">10.1007/3-540-44651-6_24</idno><idno type="ChapterID">24</idno><idno type="ChapterID">Chap24</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The problem of finding paths in networks is general and many faceted with a wide range of engineering applications in communication networks. Finding the optimal path or combination of paths usually leads to NP-hard combinatorial optimization problems. A recent and promising method, the cross-entropy method proposed by Rubinstein, manages to produce optimal solutions to such problems in polynomial time. However this algorithm is centralized and batch oriented. In this paper we show how the cross-entropy method can be reformulated to govern the behaviour of multiple mobile agents which act independently and asynchronously of each other. The new algorithm is evaluate on a set of well known Travelling Salesman Problems. A simulator, based on the Network Simulator package, has been implemented which provide realistic simulation environments. Results show good performance and stable convergence towards near optimal solution of the problems tested.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/TelematiV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003036 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 003036 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= TelematiV1
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:8AAF70A4EEDC5E11808518960B53DC10CE2D1CC1
|texte= Using the Cross-Entropy Method to Guide/Govern Mobile Agent’s Path Finding in Networks
}}
| This area was generated with Dilib version V0.6.31. |  |