search query: @keyword yhteistyö / total: 67
results-list
reference: 11 / 67
« previous | next »
Author:Halme, Antti
Title:Cooperative Heuristic Search with Software Agents
Heuristinen yhteistyöhaku ohjelmistoagenttien avulla
Publication type:Master's thesis
Publication year:2014
Pages:88      Language:   eng
Department/School:Perustieteiden korkeakoulu
Main subject:Tietojenkäsittelytiede   (IL3010)
Supervisor:Orponen, Pekka
Instructor:
Electronic version URL: http://urn.fi/URN:NBN:fi:aalto-201406252210
OEVS:
Electronic archive copy is available via Aalto Thesis Database.
Instructions
close

Reading digital theses in the closed network of the Aalto University Harald Herlin Learning Centre

In the closed network of Learning Centre you can read digital and digitized theses not available in the open network.

The Learning Centre contact details and opening hours: https://learningcentre.aalto.fi/en/harald-herlin-learning-centre/

You can read theses on the Learning Centre customer computers, which are available on all floors.

Logging on to the customer computers

  • Aalto University staff members log on to the customer computer using the Aalto username and password.
  • Other customers log on using a shared username and password.

Opening a thesis

  • On the desktop of the customer computers, you will find an icon titled:

    Aalto Thesis Database

  • Click on the icon to search for and open the thesis you are looking for from Aaltodoc database. You can find the thesis file by clicking the link on the OEV or OEVS field.

Reading the thesis

  • You can either print the thesis or read it on the customer computer screen.
  • You cannot save the thesis file on a flash drive or email it.
  • You cannot copy text or images from the file.
  • You cannot edit the file.

Printing the thesis

  • You can print the thesis for your personal study or research use.
  • Aalto University students and staff members may print black-and-white prints on the PrintingPoint devices when using the computer with personal Aalto username and password. Color printing is possible using the printer u90203-psc3, which is located near the customer service. Color printing is subject to a charge to Aalto University students and staff members.
  • Other customers can use the printer u90203-psc3. All printing is subject to a charge to non-University members.
Location:P1 Ark Aalto  1726   | Archive
Keywords:concurrency
parallel algorithm
nondeterminism
agent
cooperation
heuristic search
samanaikaisuus
rinnakkaisalgoritmi
epädeterministisyys
A*
agentti
yhteistyö
heuristinen haku
15-puzzle
Abstract (eng): Parallel algorithms extend the notion of sequential algorithms by permitting the simultaneous execution of independent computational steps.
When the independence constraint is lifted and executions can freely interact and intertwine, parallel algorithms become concurrent and may behave in a nondeterministic way.
Parallelism has over the years slowly risen to be a standard feature of high-performance computing, but concurrency, being even harder to reason about, is still considered somewhat notorious and undesirable.
As such, the implicit randomness available in concurrency is rarely made use of in algorithms.

This thesis explores concurrency as a means to facilitate algorithmic cooperation in a heuristic search setting.
We use agents, cooperating software entities, to build a single-source shortest path (SSSP) search algorithm based on parallelized A*, dubbed A!.
We show how asynchronous information sharing gives rise to implicit randomness, which cooperating agents use in A! to maintain a collective secondary ranking heuristic and focus search space exploration.

We experimentally show that A! consistently outperforms both vanilla A* and a noncooperative, explicitly randomized A* variant in the standard n-puzzle sliding tile problem context.
The results indicate that A! performance increases with the addition of more agents, but that the returns are diminishing.
A! is observed to be sensitive to heuristic improvement, but also constrained by search overhead from limited path diversity.
A hybrid approach combining both implicit and explicit randomness is also evaluated and found to not be an improvement over A! alone.

The studied A! implementation based on vanilla A* is not as such competitive against state-of-the-art parallel A* algorithms, but rather a first step in applying concurrency to speed up heuristic SSSP search.
The empirical results imply that concurrency and nondeterministic cooperation can successfully be harnessed in algorithm design, inviting further inquiry into algorithms of this kind.
Abstract (fin): Rinnakkaisalgoritmit sallivat useiden riippumattomien ohjelmakäskyjen suorittamisen samanaikaisesti.
Kun riippumattomuusrajoite poistetaan ja käskyjen suorittamisen järjestystä ei hallita, rinnakkaisalgoritmit voivat käskysuoritusten samanaikaisuuden vuoksi käyttäytyä epädeterministisellä tavalla.
Rinnakkaisuus on vuosien saatossa noussut tärkeään rooliin tietotekniikassa ja samalla hallitsematonta samanaikaisuutta on yleisesti alettu pitää ongelmallisena ja ei-toivottuna.
Samanaikaisuudesta kumpuavaa epäsuoraa satunnaisuutta hyödynnetään harvoin algoritmeissa.

Tämä työ käsittelee käskysuoritusten samanaikaisuuden hyödyntämistä osana heuristista yhteistyöhakua.
Työssä toteutetaan agenttien, yhteistyökykyisten ohjelmistokomponenttien, avulla uudenlainen A!-hakualgoritmi.
A! perustuu rinnakkaiseen A*-algoritmiin, joka ratkaisee yhden lähteen lyhimmän polun hakuongelman.
Työssä näytetään, miten ajastamaton viestintä agenttien välillä johtaa epäsuoraan satunnaisuuteen, jota A!-agentit kollektiivisesti hyödyntävät toissijaisen järjestämisheuristiikan ylläpitämisessä ja edelleen haun kohdentamisessa.

Työssä näytetään kokeellisesti, kuinka A! suoriutuu niin tavanomaista kuin satunnaistettuakin A*-algoritmia paremmin n-puzzle pulmapelin ratkaisemisessa.
Tulokset osoittavat, että A!-algoritmin suorituskyky kasvaa lisäagenttien myötä, mutta myös sen, että hyöty on joka lisäyksen jälkeen suhteellisesti pienempi.
A! osoittautuu heuristiikan hyödyntämisen osalta verrokkeja herkemmäksi, mutta myös etsintäpolkujen monimuotoisuuden kannalta vaatimattomaksi.
Yksinkertaisen suoraa ja epäsuoraa satunnaisuutta yhdistävän hybridialgoritmin ei todeta tuovan lisäsuorituskykyä A!-algoritmiin verrattuna.

Empiiriset kokeet osoittavat, että hallitsematonta samanaikaisuutta ja epädeterminististä yhteistyötä voi onnistuneesti hyödyntää algoritmisuunnittelussa, mikä kannustaa lisätutkimuksiin näitä soveltavan algoritmiikan parissa.
ED:2014-08-03
INSSI record number: 49433
+ add basket
« previous | next »
INSSI