A group testing algorithm with online informational learning

Eugene Kagan and Irad Ben-gal

IISE Transactions, 2014, vol. 46, issue 2, 164-184

Abstract: An online group testing method to search for a hidden object in a discrete search space is proposed. A relevant example is a search after a nonconforming unit in a batch, while many other applications can be related. A probability mass function is defined over the search space to represent the probability of an object (e.g., a nonconforming unit) to be located at some point or subspace. The suggested method follows a stochastic local search procedure and can be viewed as a generalization of the Learning Real-Time A* (LRTA*) search algorithm, while using informational distance measures over the searched space. It is proved that the proposed Informational LRTA* (ILRTA*) algorithm converges and always terminates. Moreover, it is shown that under relevant assumptions, the proposed algorithm generalizes known optimal information-theoretic search procedures, such as the offline Huffman search or the generalized optimum testing algorithm. However, the ILRTA* can be applied to new situations, such as a search with side information or an online search where the probability distribution changes. The obtained results can help to bridge the gap between different search procedures that are related to quality control, artificial intelligence, and information theory.

Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/0740817X.2013.803639 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:46:y:2014:i:2:p:164-184

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/0740817X.2013.803639

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().