This work addresses applications of search theory where a mobile search agent seeks to find an unknown number of stationary targets randomly distributed in a bounded search domain. We assume that the search mission is subject to a time or distance constraint, and that the local environmental conditions affect sensor performance. Because the environment varies by location, the effectiveness of the search sensor also varies by location. Our contribution to search theory includes new decision-theoretic approaches for generating optimal search plans in the presence of false alarms and uncertain environmental variability. We also formally define the value of environmental information for improving the effectiveness of a search mission, and we develop methods for optimal deployment of assets that can acquire environmental information in order to improve search effectiveness. Finally, we extend our research to the case of multiple cooperating search agents. For the case that inter-agent communication is severely bandwidth-limited, such as in subsea applications, we propose a method for assessing the expected value of inter-agent communication relative to joint search effectiveness. Our results lead to a method for determining when search agents should communicate. Our contributions to search theory address important applications that range from subsea mine-hunting to post-disaster search and rescue applications. / PHD / We address search applications where a mobile search agent seeks to find an unknown number of stationary targets randomly distributed in a bounded search domain. The search agent is equipped with a search sensor that detects the targets at a location. Sensor measurements are often imperfect due to possible missed detections and false alarms. We also consider that the local environmental conditions affect the quality of the data acquired from the search sensor. For instance, if we are searching for a target that has a rocky shape, we expect that it will be harder to find that target in a rocky environment. We consider that the search mission is subject to a time or distance constraint, and thus, search can be performed on only a subset of locations. Our goal in this study is to formally determine where to acquire the search measurements so that the search effectiveness can be maximized. We also formally define the value of acquiring environmental information for improving the effectiveness of a search mission, and we develop methods for optimal deployment of assets that can acquire environmental information in order to improve search effectiveness. Finally, we address the cases where multiple search assets collaboratively search the environment and they can communicate their local information with each other. We are particularly interested in determining when a vehicle should communicate with another vehicle so that the joint search effectiveness can be improved. Our contributions to search theory address important applications that range from subsea mine-hunting to post-disaster search and rescue applications.

Search and Rescue (SAR) operations aim at finding missing objects with minimum time in a determined area. There are fundamentally two problems in these operations. The first problem is assessing highly reliable probability distribution maps, and the second is determining the search pattern that sweeps the area from the air as fast as possible. In this study, geographic information systems (GIS) and multi criteria decision analysis (MCDA) are integrated and a new model is developed based upon Search Theory in order to find the position of the missing object as quickly as possible with optimum resource allocation. Developed model is coded as a search planning tool for the use of search and rescue planners. Inputs of the model are last known position of the missing object and related clues about its probable position. In the developed model, firstly related layers are arranged according to their priorities based on subjective expert opinion. Then a multi criteria decision method is selected and each data layer is multiplied by a weight corresponding to search expert&rsquo / s rank. Then a probability map is established according to the result of MCDA methods. In the second phase, the most suitable search patterns used in literature are applied based on established probability map. The developed model is a new approach to shortening the time in SAR operations and finding the suitable search pattern for the data of different crashes.

At its core, this dissertation examines the role of information, particularly as it relates to proxies for quality, and how it affects both donor and organization decision processes in the humanitarian space. In Chapter 2 I consider the context of competition within the sub-sector of international humanitarian relief organizations. It has been observed that large scale humanitarian relief events tend to spawn highly competitive environments in which organizations compete with one another for publicity and funding, often times to the detriment of effective resource utilization. The question of why altruistic organizations behave in this manner arises. Positing that competition is a result of dual organization objectives and the inability to credibly signal quality a model of signaling is presented to explain this phenomenon, and conditions under which pooling and separating equilibrium can occur are shown. Results are shown to match closely with observed behavior, and potential policy remedies are considered using the model as a foundation. Chapter 3 addresses a similar question but broadens the analysis to that of a general market for charitable goods. Building on foundational results in search theory, I propose a two-stage model of donor search behavior to explain the effects of transparency and exposure on both donor and organization behavior as it regards how donors select organizations. Using both analytical and simulated results I show how donor behavior changes under various market constructions, with implications on total market outcomes and organization behavior discussed. Chapter 4 concludes with an empirical analysis to test the assumptions and results from the models of Chapters 2 and 3. Using an observational data set provided by the online charitable giving marketplace GlobalGiving, fixed effects panel regression and logit models are used to investigate the effects of transparency on both the amount of a donor's gift, and on the likelihood of repeat giving. Results are complicated by discussed validity issues, and in general show that within the context of GlobalGiving proxied transparency does not appear to have a significant practical effect on either the amount of the gift or organization selection by a given donor. While some significance is shown for various constructions, the results are not shown to be robust. A discussion of the results within the context of the donor search model of Chapter 3 is also provided.

Nearest-neighbor search is a very natural and universal problem in computer science. Often times, the problem size necessitates approximation. In this thesis, I present new paradigms for nearest-neighbor search (along with new algorithms and theory in these paradigms) that make nearest-neighbor search more usable and accurate. First, I consider a new notion of search error, the rank error, for an approximate neighbor candidate. Rank error corresponds to the number of possible candidates which are better than the approximate neighbor candidate. I motivate this notion of error and present new efficient algorithms that return approximate neighbors with rank error no more than a user specified amount. Then I focus on approximate search in a scenario where the user does not specify the tolerable search error (error constraint); instead the user specifies the amount of time available for search (time constraint). After differentiating between these two scenarios, I present some simple algorithms for time constrained search with provable performance guarantees. I use this theory to motivate a new space-partitioning data structure, the max-margin tree, for improved search performance in the time constrained setting. Finally, I consider the scenario where we do not require our objects to have an explicit fixed-length representation (vector data). This allows us to search with a large class of objects which include images, documents, graphs, strings, time series and natural language. For nearest-neighbor search in this general setting, I present a provably fast novel exact search algorithm. I also discuss the empirical performance of all the presented algorithms on real data.

Thesis (M.App.Sc.) - Carleton University, 2005. / Includes bibliographical references (p. 172-178). Also available in electronic format on the Internet.

This thesis presents how unmanned aerial vehicles (UAVs) can successfully assist in search and rescue (SAR) operations using wireless localization. The zone-grid to partition to capture/detect WiFi probe requests follows the concepts found in Search Theory Method. The UAV has attached a sensor, e.g., WiFi sniffer, to capture/detect the WiFi probes from victims or lost people’s smartphones. Applying the Random-Forest based machine learning algorithm, an estimation of the user's location is determined with a 81.8% accuracy. UAV technology has shown limitations in the navigational performance and limited flight time. Procedures to optimize these limitations are presented. Additionally, how the UAV is maneuvered during flight is analyzed, considering different SAR flight patterns and Li-Po battery consumption rates of the UAV. Results show that controlling the UAV by remote-controll detected the most probes, but it is less power efficient compared to control it autonomously.

一般醫療經濟文獻上認為在資訊不對稱的情形下，醫療市場中並不存在消費者主權，是而分析時僅由醫師的角度看問題。事實上，消費者主權扮演決定性的重要地位。我們認為病人是處於積極、主動之地位，而非一味相信信醫師；且病人會（某一定程度的）自己根據醫師提供之醫療服務數量及其品質（病人能夠意識到的；主觀的）做為判斷之根據。本文以消費者搜尋行為模型化病人與醫師的關係，正可將消費者主權在醫療市場中扮演的角色，明確且清楚的表現出來。 　　我們接受醫師為病人代理人的說法，但彌補了文獻上的不足。本文以消費者搜尋行為做為一種機制，使醫師與病人間並不明顯的契約得以進行，並能使結果更具效率性。以消費者搜尋模型將此一機制模型化後，並進一步分析若外生條件發生改變時，對此一機制的影響。 　　此外，在一般的醫療服務文獻中，其所謂的醫療服務事實上，應包括了本文所提及的服務量及品質兩種觀念，醫療服務品質常須透過購買及親自經驗後對其效用之影響，方能得知，此點有別於數量之購買。我們嘗試將兩者分開討論。 　　醫師不一定對病人有正的誘發，也有負的誘發之可能。然而醫師對病人的誘發是正是負，則決定於報酬給付制度；而誘發程度則決定於醫師的偏好、及病人擁有資訊之情形。

Arrow and Raynaud introduced a set of axioms that a ranking rule should verify. Among these, axiom V' states that the compromise ranking should be a so-called prudent order. Intuitively, a prudent order is a linear order such that the strongest opposition against this solution is minimal. Since the related literature lacks in solid theoretical foundations for this type of aggregation rule, it was our main objective in this thesis to thoroughly study and gain a better understanding of the family of prudent ranking rules. We provide characterizations of several prudent ranking rules in a conjoint axiomatic framework. We also prove that we can construct profiles for which the result of a prudent ranking rule and a non-prudent ranking rule can be contradictory. Finally we illustrate the use of prudent ranking rules in a group decision context and on the composite indicator problem.<p><p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Today more and more different types of autonomous robots and vehicles are being developed. Most of these rely on the global positioning system and/or communication with other robots and vehicles to determine their global position. However, these are not viable options for the autonomous underwater vehicles (AUVs) of today since radio-waves does not travel well in water. Instead, various techniques for determining the AUVs position are used which comes with a margin of error. This thesis examines the problem of efficiently performing a local search within this margin of error with the objective of finding a docking-station or a bouy.To solve this problem research was made on the subject of search theory and how it previously has been applied in this context. What was found was that classical bayesian search theory had not been used very often in this context since it would require to much processing power to be a viable option in the embedded systems that is AUVs. Instead different heuristics were used to get solutions that still were viable for the situations in which they were used, even though they maybe wasn’t optimal.Based on this the search-strategies Spiral, Greedy, Look-ahead and Quadtree were developed and evaluated in a simulator. Their mean time to detection (MTTD) were compared as well as the average time it took for the strategies to process a search. Look-ahead was the best one of the four different strategies with respect to the MTTD and based on this it is suggested that it should be implemented and evaluated in a real AUV. / Idag utvecklas allt fler olika typer av autonoma robotar och fordon. De flesta av dessa är beroende av det globala positioneringssystemet och/eller kommunikation med andra robotar och fordon för att bestämma deras globala position. Detta är dock inte realistiska alternativ för autonoma undervattensfordon (AUV) idag eftersom radiovågor inte färdas bra i vatten. I stället används olika tekniker för att bestämma AUVens position, tekniker som ofta har en felmarginal. Denna rapport undersöker problemet med att effektivt utföra en lokal sökning inom denna felmarginal med målet att hitta en dockningsstation eller en boj.För att lösa detta problem gjordes en litteraturstudie om ämnet sökteori och hur det tidigare har tillämpats i detta sammanhang. Det som hittades var att den klassiska bayesiska sökteorin inte hade använts mycket ofta i detta sammanhang eftersom det skulle kräva för mycket processorkraft för att det skulle vara ett rimligt alternativ för de inbyggda systemen på en AUV. Istället användes olika heuristiska metoder för att få lösningar som fortfarande var dugliga för de situationer där de användes, även om de kanske inte var optimala.Baserat på detta utvecklades sökstrategierna Spiral, Greedy, Look-ahead och Quad-tree och utvärderades i en simulator. Deras genomsnittliga tid för att upptäcka målet (MTTD) jämfördes liksom den genomsnittliga tiden det tog för strategierna att bearbeta en sökning. Look-ahead var den bästa av de fyra olika strategierna med avseende på MTTD och baserat på detta föreslås det att den ska implementeras och utvärderas i en verklig AUV.

Approved for public release; distribution is unlimited / An increasing number of unmanned vehicles (UV) are being incorporated into maritime operations as organic elements of Expeditionary and Carrier Strike Groups for development of the recognized maritime picture. This thesis develops an analytically-based planning aid for allocating UVs to missions. Inputs include the inventory of UVs, sensors, their performance parameters, and operational scenarios. Operations are broken into mission critical functions: detection, identification, and collection. The model output assigns aggregated packages of UVs and sensors to one of the three functions within named areas of interest. A spreadsheet model uses conservative time-speed-distance calculations, and simplified mathematical models from search theory and queuing theory, to calculate measures of performance for possible assignments of UVs to missions. The spreadsheet model generates a matrix as input to a linear integer program assignment model which finds the best assignment of UVs to missions based on the user inputs and simplified models. The results provide the mission planner with quantitatively-based recommendations for unmanned vehicle mission tasking in challenging scenarios. / Lieutenant, United States Navy