Planning under uncertainty for large-scale problems with applications to wireless networking

Joni Pajarinen

Planning under uncertainty for large-scale problems with applications to wireless networking

Julkaisun otsikon käännös: Päätöksenteko epävarmuuden vallitessa suurissa ongelmissa ja sovelluksia langattomaan tiedonsiirtoon

Joni Pajarinen

Tutkimustuotos: Doctoral Thesis › Collection of Articles

Abstrakti

Toimintojen suunnittelu tulevaisuuteen on tärkeä tehtävä useissa käytännön ongelmissa. Epävarmuus toimintojen lopputuloksesta ja vaillinaiset kohinaiset havainnot tekevät suunnittelusta usein vaikeaa. Erityisesti langattomissa verkoissa langattomien agenttien täytyy päättää milloin lähettää dataa, käyttäen ainoastaan kohinaisia havaintoja ja vaillinaista tietoa verkkoliikenteestä ja muiden laitteiden tilasta. Useissa tämänkaltaisissa tilanteissa osittain havaittava Markov-päätösprosessi (POMDP)-malli määrittelee optimaaliset toiminnot yhdelle agentille ja hajautettu POMDP (DEC-POMDP)-malli usealle yhteistyötä tekevälle agentille. Tämä väitöskirja esittelee uusia tehokkaita menetelmiä näille ilmaisukykyisille, mutta laskennallisesti vaativille POMDP ja DEC-POMDP-malleille. Uudet vaativat langattomat sovellukset toimivat motivaationa menetelmille. Tämän väitöskirjan ensimmäinen kontribuutio on faktoroitu POMDP-menetelmä, joka ratkaisee suurempia ongelmia kuin vertailumenetelmät. Toinen kontribuutio on ensimmäinen ehdotettu faktoroitu äärettömän horisontin DEC-POMDP-menetelmä, joka ratkaisee pienempiä ongelmia samalla tarkkuudella ja suurempia ongelmia kuin ei-faktoroidut vertailumenetelmät. Kolmas kontribuutio esittelee uudentyyppisen jaksollisen tilakonesäätimen POMDP ja DEC-POMDP-malleille, jonka avulla voidaan optimoida suurempia tilakonesäätimiä paremmalla suorituskyvyllä kuin aikaisemmilla menetelmillä. Neljäs kontribuutio on POMDP-malli kognitiiviselle radiolaitteelle, joka lähettää vanhoille radiolaitteille varatuilla taajuuskanavilla. Malli ottaa huomioon vanhojen radiolaitteiden erilaiset purskepituudet ja reaktiot ja suoriutuu paremmin kokeissa kuin vertailumallit. Viidennessä kontribuutiossa usean laitteen langaton lähetys spatiaalisen häiriön alla muotoillaan faktoroiduksi DEC-POMDP:ksi. Tämä sallii optimoinnin sekä tilan että ajan suhteen, ja lähestymistavalla saavutetaan kokeissa parempia tuloksia kuin langattomaan tiedonsiirtoon käytetyillä vertailumenetelmillä. Langattomien laitteiden päätösten laatu riippuu ratkaisevasti havaintojen hinnasta ja laadusta. Väitöskirjan viimeinen kontribuutio on uusi kaistantunnistustapa, joka käyttää nanoteknologiaan pohjautuvaa laskentaa. Uudessa tunnistustavassa koneoppimista käytetään nanomittakaavan vikojen vaimentamiseen ja signaalien luokitteluun.

Julkaisun otsikon käännös	Päätöksenteko epävarmuuden vallitessa suurissa ongelmissa ja sovelluksia langattomaan tiedonsiirtoon
Alkuperäiskieli	Englanti
Pätevyys	Tohtorintutkinto
Myöntävä instituutio	Aalto-yliopisto
Valvoja/neuvonantaja	Oja, Erkki, Vastuuprofessori Peltonen, Jaakko, Ohjaaja
Kustantaja	Aalto University
Painoksen ISBN	978-952-60-4998-4
Sähköinen ISBN	978-952-60-4999-1
Tila	Julkaistu - 2013
OKM-julkaisutyyppi	G5 Artikkeliväitöskirja

Tutkimusalat

Päätöksenteko
POMDP
DEC-POMDP
langaton verkko
WLAN
kognitiivinen radio
nanolaskenta

Pääsy asiakirjaan

http://urn.fi/URN:ISBN:978-952-60-4999-1

Siteeraa tätä

@phdthesis{acc0900edc9a41aebec8d64fe1c7a3af,

title = "Planning under uncertainty for large-scale problems with applications to wireless networking",

abstract = "Planning actions into the future is a fundamental task in many real world problems. The uncertain outcome of actions and partial noisy observations often make planning difficult. Specifically, in a wireless network, wireless agents must reason whether to transmit data now or postpone transmission into the future, based only on noisy sensor readings and incomplete information about traffic patterns and the state of other devices. In many settings of this kind, a partially observable Markov decision process (POMDP) defines optimal actions for a single agent and a decentralized POMDP (DEC-POMDP) for multiple co-operative agents. POMDPs and DEC-POMDPs are expressive but computationally demanding models. This thesis presents new efficient POMDP and DEC-POMDP methods, motivated by challenging new wireless networking problems. The first contribution of this thesis is a method for large factored POMDPs that handles larger problems than the comparison methods. The second contribution is the first proposed method for general factored infinite-horizon DEC-POMDPs. The method solves smaller problems with similar accuracy as non-factored methods and it can solve larger problems than the comparison methods. The third contribution is a new kind of controller type for POMDPs and DEC-POMDPs, a periodic finite state controller, that allows optimization of larger controllers than previous finite state controller approaches and yields higher performance. The fourth contribution is a POMDP model for a cognitive radio device, which served as motivation for the factored POMDP method. In the model, the cognitive radio transmits on frequency channels occupied by high priority legacy users. The model takes into account varying network traffic burst lengths and reactions of legacy users and performs better than the comparison models. The fifth contribution consists of framing wireless channel access of multiple devices with complicated spatial interference as a factored DEC-POMDP. This allows optimizing over both the spatial and time dimensions and in experiments yields higher performance than the wireless comparison methods. The quality of wireless device decisions depends crucially on the cost and quality of sensor readings. The last contribution is a new spectrum sensing approach, that uses nanotechnology based computations and machine learning for mitigating nanoscale faults and classifying radio signals.",

keywords = "Planning, POMDP, DEC-POMDP, wireless network, WLAN, cognitive radio, nanocomputing, P{\"a}{\"a}t{\"o}ksenteko, POMDP, DEC-POMDP, langaton verkko, WLAN, kognitiivinen radio, nanolaskenta, Planning, POMDP, DEC-POMDP, wireless network, WLAN, cognitive radio, nanocomputing",

author = "Joni Pajarinen",

year = "2013",

language = "English",

isbn = "978-952-60-4998-4",

series = "Aalto University publication series DOCTORAL DISSERTATIONS",

publisher = "Aalto University",

number = "20",

address = "Finland",

school = "Aalto University",

}

TY - BOOK

T1 - Planning under uncertainty for large-scale problems with applications to wireless networking

AU - Pajarinen, Joni

PY - 2013

Y1 - 2013

N2 - Planning actions into the future is a fundamental task in many real world problems. The uncertain outcome of actions and partial noisy observations often make planning difficult. Specifically, in a wireless network, wireless agents must reason whether to transmit data now or postpone transmission into the future, based only on noisy sensor readings and incomplete information about traffic patterns and the state of other devices. In many settings of this kind, a partially observable Markov decision process (POMDP) defines optimal actions for a single agent and a decentralized POMDP (DEC-POMDP) for multiple co-operative agents. POMDPs and DEC-POMDPs are expressive but computationally demanding models. This thesis presents new efficient POMDP and DEC-POMDP methods, motivated by challenging new wireless networking problems. The first contribution of this thesis is a method for large factored POMDPs that handles larger problems than the comparison methods. The second contribution is the first proposed method for general factored infinite-horizon DEC-POMDPs. The method solves smaller problems with similar accuracy as non-factored methods and it can solve larger problems than the comparison methods. The third contribution is a new kind of controller type for POMDPs and DEC-POMDPs, a periodic finite state controller, that allows optimization of larger controllers than previous finite state controller approaches and yields higher performance. The fourth contribution is a POMDP model for a cognitive radio device, which served as motivation for the factored POMDP method. In the model, the cognitive radio transmits on frequency channels occupied by high priority legacy users. The model takes into account varying network traffic burst lengths and reactions of legacy users and performs better than the comparison models. The fifth contribution consists of framing wireless channel access of multiple devices with complicated spatial interference as a factored DEC-POMDP. This allows optimizing over both the spatial and time dimensions and in experiments yields higher performance than the wireless comparison methods. The quality of wireless device decisions depends crucially on the cost and quality of sensor readings. The last contribution is a new spectrum sensing approach, that uses nanotechnology based computations and machine learning for mitigating nanoscale faults and classifying radio signals.

AB - Planning actions into the future is a fundamental task in many real world problems. The uncertain outcome of actions and partial noisy observations often make planning difficult. Specifically, in a wireless network, wireless agents must reason whether to transmit data now or postpone transmission into the future, based only on noisy sensor readings and incomplete information about traffic patterns and the state of other devices. In many settings of this kind, a partially observable Markov decision process (POMDP) defines optimal actions for a single agent and a decentralized POMDP (DEC-POMDP) for multiple co-operative agents. POMDPs and DEC-POMDPs are expressive but computationally demanding models. This thesis presents new efficient POMDP and DEC-POMDP methods, motivated by challenging new wireless networking problems. The first contribution of this thesis is a method for large factored POMDPs that handles larger problems than the comparison methods. The second contribution is the first proposed method for general factored infinite-horizon DEC-POMDPs. The method solves smaller problems with similar accuracy as non-factored methods and it can solve larger problems than the comparison methods. The third contribution is a new kind of controller type for POMDPs and DEC-POMDPs, a periodic finite state controller, that allows optimization of larger controllers than previous finite state controller approaches and yields higher performance. The fourth contribution is a POMDP model for a cognitive radio device, which served as motivation for the factored POMDP method. In the model, the cognitive radio transmits on frequency channels occupied by high priority legacy users. The model takes into account varying network traffic burst lengths and reactions of legacy users and performs better than the comparison models. The fifth contribution consists of framing wireless channel access of multiple devices with complicated spatial interference as a factored DEC-POMDP. This allows optimizing over both the spatial and time dimensions and in experiments yields higher performance than the wireless comparison methods. The quality of wireless device decisions depends crucially on the cost and quality of sensor readings. The last contribution is a new spectrum sensing approach, that uses nanotechnology based computations and machine learning for mitigating nanoscale faults and classifying radio signals.

KW - Planning

KW - POMDP

KW - DEC-POMDP

KW - wireless network

KW - WLAN

KW - cognitive radio

KW - nanocomputing

KW - Päätöksenteko

KW - POMDP

KW - DEC-POMDP

KW - langaton verkko

KW - WLAN

KW - kognitiivinen radio

KW - nanolaskenta

KW - Planning

KW - POMDP

KW - DEC-POMDP

KW - wireless network

KW - WLAN

KW - cognitive radio

KW - nanocomputing

M3 - Doctoral Thesis

SN - 978-952-60-4998-4

T3 - Aalto University publication series DOCTORAL DISSERTATIONS

PB - Aalto University

ER -

Planning under uncertainty for large-scale problems with applications to wireless networking

Abstrakti

Tutkimusalat

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä