東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Optimizing sensing: Theory and appli...

Carnegie Mellon University.

FindBook

Google Book

Amazon

博客來

Optimizing sensing: Theory and applications.

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Optimizing sensing: Theory and applications./
作者:	Krause, Andreas.
面頁冊數:	328 p.
附註:	Adviser: Carlos Guestrin.
Contained By:	Dissertation Abstracts International70-01B.
標題:	Computer Science. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3343461
ISBN:	9780549983491

Optimizing sensing: Theory and applications.
Krause, Andreas.

Optimizing sensing: Theory and applications. - 328 p.

Adviser: Carlos Guestrin.

Thesis (Ph.D.)--Carnegie Mellon University, 2008.

Many practical applications, such as environmental monitoring or placing sensors for event detection, require to select among a set of informative but possibly expensive observations. When monitoring spatial phenomena with sensor networks or mobile robots, for example, we need to decide which locations to observe in order to most effectively decrease the uncertainty, at minimum cost. These problems are usually NP-hard. Previous approaches for tackling these sensing problems have mainly relied on myopic heuristics, i.e., approaches which only consider the next best observation to add, without planning ahead for future sensing opportunities. For those approaches, typically no performance guarantees are known. Existing nonmyopic approaches have involved computationally intensive techniques which are very difficult to scale to larger problems.

ISBN: 9780549983491Subjects--Topical Terms:

626642
Computer Science.

Optimizing sensing: Theory and applications.
LDR:05396nam 2200349 a 45 001 861268
005 20100719
008 100719s2008 ||||||||||||||||| ||eng d
020 $a 9780549983491
035 $a (UMI)AAI3343461
035 $a AAI3343461
040 $a UMI $c UMI
100 1 $a Krause, Andreas. $3 724485
245 1 0 $a Optimizing sensing: Theory and applications.
300 $a 328 p.
500 $a Adviser: Carlos Guestrin.
500 $a Source: Dissertation Abstracts International, Volume: 70-01, Section: B, page: 0405.
502 $a Thesis (Ph.D.)--Carnegie Mellon University, 2008.
520 $a Many practical applications, such as environmental monitoring or placing sensors for event detection, require to select among a set of informative but possibly expensive observations. When monitoring spatial phenomena with sensor networks or mobile robots, for example, we need to decide which locations to observe in order to most effectively decrease the uncertainty, at minimum cost. These problems are usually NP-hard. Previous approaches for tackling these sensing problems have mainly relied on myopic heuristics, i.e., approaches which only consider the next best observation to add, without planning ahead for future sensing opportunities. For those approaches, typically no performance guarantees are known. Existing nonmyopic approaches have involved computationally intensive techniques which are very difficult to scale to larger problems.
520 $a In this Thesis, we present a new class of approaches for observation selection, using techniques from combinatorial optimization. We show that many observation selection objectives satisfy submodularity, an intuitive diminishing returns property---adding a sensor to a small deployment helps more than adding it to a large deployment. Examples include mutual information for spatial prediction and placing sensors for outbreak detection.
520 $a We also develop a suite of non-greedy approaches that systematically exploit this submodularity property in order to efficiently obtain provably near-optimal solutions to complex sensing problems. For example, the chosen observations often need to be robust against sensor failure or uncertainty about model parameters. Examples include minimizing the maximum posterior variance in spatial prediction and robust experimental design. We show, that many such problems require the optimization of an adversarially chosen submodular objective function. We will demonstrate that for this problem, existing greedy algorithms perform arbitrarily badly. We develop an algorithm, SATURATE, which performs near-optimally in this setting.
520 $a In addition to the problem of finding the best k observations (sensor locations), we consider problems with complex combinatorial constraints. For example, when placing wireless sensor networks, the chosen locations should not only be very informative, but also allow efficient communication. When using robots for making observations, the chosen locations need to lie on a collection of paths. We present PSPIEL, an efficient algorithm which finds solutions which near-optimally trade off sensing quality and cost.
520 $a When deploying wireless sensor networks, another fundamental constraint is battery lifetime. Since every measurement draws power, sensors can typically be activated only a fraction of the time. Hence, the problem of scheduling the sensors becomes of crucial importance. Traditionally, sensor placement and scheduling have been considered separately from each other. In this Thesis, we present ESPASS, an efficient algorithm for simultaneously optimizing the placement and scheduling. We show that this simultaneous approach leads to drastic improvements in network lifetime when compared to the traditional, stage-wise approach.
520 $a A key question in many observation selection problems is how much better a sequential algorithm, which decides on the next observation based on previous observations, can perform when compared to the best fixed set of observations chosen a priori. We present a partial answer to the question for spatial prediction in Gaussian Processes. We develop a theoretical bound quantifying the gap between the best sequential and a priori selections, and use it to develop an exploration---exploitation approach for active learning in Gaussian Processes.
520 $a Lastly, we look beyond submodular observation selection problems, and consider the problem of selecting optimal observations in graphical models. We show that in chain-graphical (Markovian) models, it is possible to efficiently find the optimal sequential policy. However, even for slightly larger classes of graphical models, we prove strong hardness results.
520 $a In addition to providing algorithms and theoretical analyses, we present extensive empirical evaluation of our approaches on several real-world case studies. These include building a sensing chair for posture recognition, monitoring environmental phenomena with mobile robots, securing municipal water distribution networks, and selecting informative weblogs to read on the Internet.
590 $a School code: 0041.
650 4 $a Computer Science. $3 626642
690 $a 0984
710 2 $a Carnegie Mellon University. $3 1018096
773 0 $t Dissertation Abstracts International $g 70-01B.
790 $a 0041
790 1 0 $a Guestrin, Carlos, $e advisor
791 $a Ph.D.
792 $a 2008
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3343461