Author name cluster

Mark Levene

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

IROS Conference 2008 Conference Paper

HybridExploration: A distributed approach to terrain exploration using mobile and fixed sensor nodes

Ettore Ferranti
Niki Trigoni
Mark Levene

When an emergency occurs within a building, it may be initially safer to send autonomous mobile nodes, instead of human responders, to explore the area and identify hazards and victims. Exploring all the area in the minimum amount of time and reporting back interesting findings to the human personnel outside the building is an essential part of rescue operations. Our assumptions are that the area map is unknown, there is no existing network infrastructure, long-range wireless communication is unreliable and nodes are not location-aware. We take into account these limitations, and propose a novel algorithm, HybridExploration, that makes use of both mobile nodes (robots, called agents) and stationary nodes (inexpensive smart devices, called tags). As agents enter the emergency area, they sprinkle tags within the space to label the environment with states. By reading and updating the state of the local tags, agents are able to coordinate indirectly with each other, without relying on direct agent-to-agent communication. In addition, tags wirelessly exchange local information with nearby tags to further assist agents in their exploration task. Our simulation results show that the proposed algorithm, which exploits both tag-to-tag and agent-to-tag communication, outperforms previous algorithms that rely only on agent-to-tag communication.

Details

TCS Journal 2008 Journal Article

Modelling the navigation potential of a web page

Trevor Fenner
Mark Levene
George Loizou

Navigating the web involves pruning (or discounting) some of the outgoing links and following one of the others. More pruning is likely to happen for deeper navigation. Under this model of navigation, we call the number of nodes that are available after pruning, for browsing within a session, the potential gain of the starting web page. We first consider the case when the discounting factor is geometric. We show that the distribution of the effective number of links that the user can follow at each navigation step after pruning, i. e. the number of nodes added to the potential gain at that step, is given by the erf function, which is related to the probability density function for the Normal distribution. We derive an approximation to the potential gain of a web page and show numerically that it is very accurate; we also obtain lower and upper bounds. We then consider a harmonic discounting factor and show that, in this case, the potential gain at each step is closely related to the probability density function for the Poisson distribution. The potential gain has been applied to web navigation where, given no other information, it helps the user to choose a good starting point for initiating a “surfing” session. Another application is in social network analysis, where the potential gain could provide a novel measure of centrality.

Details DOI

JAAMAS Journal 2008 Journal Article

Rapid exploration of unknown areas through dynamic deployment of mobile and stationary sensor nodes

Ettore Ferranti
Niki Trigoni
Mark Levene

Abstract When an emergency occurs within a building, it may be initially safer to send autonomous mobile nodes, instead of human responders, to explore the area and identify hazards and victims. Exploring all the area in the minimum amount of time and reporting back interesting findings to the human personnel outside the building is an essential part of rescue operations. Our assumptions are that the area map is unknown, there is no existing network infrastructure, long-range wireless communication is unreliable and nodes are not location-aware. We take into account these limitations, and propose an architecture consisting of both mobile nodes (robots, called agents) and stationary nodes (inexpensive smart devices, called tags). As agents enter the emergency area, they sprinkle tags within the space to label the environment with states. By reading and updating the state of the local tags, agents are able to coordinate indirectly with each other, without relying on direct agent-to-agent communication. In addition, tags wirelessly exchange local information with nearby tags to further assist agents in their exploration task. Our simulation results show that the proposed algorithm, which exploits both tag-to-tag and agent-to-tag communication, outperforms previous algorithms that rely only on agent-to-tag communication.

Details DOI

ICRA Conference 2007 Conference Paper

Brick & Mortar: an on-line multi-agent exploration algorithm

Ettore Ferranti
Niki Trigoni
Mark Levene

When an emergency occurs within a building, it is critical to explore the area as fast as possible in order to find victims and identify hazards. We propose Brick& Mortar, an algorithm for the autonomous exploration of unknown terrains by a team of mobile nodes, referred to as agents. Because of the unreliability and short range of wireless communications in an indoor environment we suggest that agents communicate indirectly with each other by tagging the environment. Agents have no prior knowledge of the terrain map, but are able to coordinate in order to explore a variety of terrains with different topological features. In our experimental evaluation, we show that Brick&Mortar significantly outperforms the competing algorithms, namely Ants and Multiple Depth First Search, in terms of exploration time. The observed performance benefits suggest that our algorithm is suitable for safety-critical applications that require rapid area coverage for real-time event detection and response.

Details

TCS Journal 2001 Journal Article

Guaranteeing no interaction between functional dependencies and tree-like inclusion dependencies

Mark Levene
George Loizou

Functional dependencies (FDs) and inclusion dependencies (INDs) are the most fundamental integrity constraints that arise in practice in relational databases. A given set of FDs does not interact with a given set of INDs if logical implication of any FD can be determined solely by the given set of FDs, and logical implication of any IND can be determined solely by the given set of INDs. The set of tree-like INDs constitutes a useful subclass of INDs whose implication problem is polynomial time decidable. We exhibit a necessary and sufficient condition for a set of FDs and tree-like INDs not to interact; this condition can be tested in polynomial time.

Details DOI

AIJ Journal 2001 Journal Article

The effect of mobility on minimaxing of game trees with random leaf values

Mark Levene
Trevor I. Fenner

Random minimaxing, introduced by Beal and Smith [ICCA J. 17 (1994) 3–9], is the process of using a random static evaluation function for scoring the leaf nodes of a full width game tree and then computing the best move using the standard minimax procedure. The experiments carried out by Beal and Smith, using random minimaxing in Chess, showed that the strength of play increases as the depth of the lookahead is increased. We investigate random minimaxing from a combinatorial point of view in an attempt to gain a better understanding of the utility of the minimax procedure and a theoretical justification for the results of Beal and Smith's experiments. The concept of domination is central to our theory. Intuitively, one move by white dominates another move when choosing the former move would give less choice for black when it is black's turn to move, and subsequently more choice for white when it is white's turn to move. We view domination as a measure of mobility and show that when one move dominates another then its probability of being chosen is higher. We then investigate when the probability of a “good” move relative to the probability of a “bad” move increases with the depth of search. We show that there exist situations when increased depth of search is “beneficial” but that this is not always the case. Under the assumption that each move is either “good” or “bad”, we are able to state sufficient conditions to ensure that increasing the depth of search increases the strength of play of random minimaxing. If the semantics of the game under consideration match these assumptions then it is fair to say that random minimaxing appears to follow a reasonably “intelligent” strategy. In practice domination does not always occur, so it remains an open problem to find a more general measure of mobility in the absence of domination.

Details DOI

TCS Journal 1998 Journal Article

Axiomatisation of functional dependencies in incomplete relations

Mark Levene
George Loizou

Incomplete relations are relations which contain null values, whose meaning is “value is at present unknown”. Such relations give rise to two types of functional dependency (FD). The first type, called the strong FD (SFD), is satisfied in an incomplete relation if for all possible worlds of this relation the FD is satisfied in the standard way. The second type, called the weak FD (WFD), is satisfied in an incomplete relation if there exists a possible world of this relation in which the FD is satisfied in the standard way. We exhibit a sound and complete axiom system for both strong and weak FDs, which takes into account the interaction between SFDs and WFDs. An interesting feature of the combined axiom system is that it is not k-ary for any natural number k ⩾ 0. We show that the combined implication problem for SFDs and WFDs can be solved in time polynomial in the size of the input set of FDs. Finally, we show that Armstrong relations exist for SFDs and WFDs.

Details DOI

I&C Journal 1997 Journal Article

Null Inclusion Dependencies in Relational Databases

Mark Levene
George Loizou

Functional dependencies (FDs) and inclusion dependencies (INDs) are the most fundamental integrity constraints that arise in practice in relational databases. We introduce null inclusion dependencies (NINDs) to cater for the situation when a database is incomplete and contains null values. We show that the implication problem for NINDs is the same as that for INDs. We then present a sound and complete axiom system for null functional dependencies (NFDs) and NINDs, and prove that the implication problem for NFDs and NINDs is decidable and EXPTIME-complete. By contrast, when no nulls are allowed, this implication problem is undecidable. This undecidability result has motivated several researchers to restrict their attention to FDs and noncircular INDs in which case the implication problem was shown to be EXPTIME- complete. Our results imply that when considering nulls in relational database design we need not assume that NINDs are noncircular.

Details DOI