Tight analysis of the (1+1)-EA for the single source shortest path problem

We conduct a rigorous analysis of the (1+1) evolutionary algorithm for the single source shortest path problem proposed by Scharnow, Tinnefeld, and Wegener (The analyses of evolutionary algorithms on sorting and shortest paths problems, 2004, Journal of Mathematical Modelling and Algorithms, 3(4):349-366). We prove that with high probability, the optimization time is O(n2 max{?, log(n)}), where ? is the smallest integer such that any vertex can be reached from the source via a shortest path having at most ? edges. This bound is tight. For all values of n and ? we provide a graph with edge weights such that, with high probability, the optimization time is of order Ω(n2 max{?, log(n)}). To obtain such sharp bounds, we develop a new technique that overcomes the coupon collector behavior of previously used arguments. Also, we exhibit a simple Chernoff type inequality for sums of independent geometrically distributed random variables, and one for sequences of random variables that are not independent, but show a desired behavior independent of the outcomes of the previous random variables. We are optimistic that these tools find further applications in the analysis of evolutionary algorithms.     

Visual comparability of 3D regular sampling and reconstruction

The Body-Centered Cubic (BCC) and Face-Centered Cubic (FCC) lattices have been analytically shown to be more efficient sampling lattices than the traditional Cartesian Cubic (CC) lattice, but there has been no estimate of their visual comparability. Two perceptual studies (each with N = 12 participants) compared the visual quality of images rendered from BCC and FCC lattices to images rendered from the CC lattice. Images were generated from two signals: the commonly used Marschner-Lobb synthetic function and a computed tomography scan of a fish tail. Observers found that BCC and FCC could produce images of comparable visual quality to CC, using 30-35 percent fewer samples. For the images used in our studies, the L(2) error metric shows high correlation with the judgement of human observers. Using the L(2) metric as a proxy, the results of the experiments appear to extend across a wide range of images and parameter choices.     

Information-based adaptive fast-forward for visual surveillance

Automated video analysis lacks reliability when searching for unknown events in video data. The practical approach is to watch all the recorded video data, if applicable in fast-forward mode. In this paper we present a method to adapt the playback velocity of the video to the temporal information density, so that the users can explore the video under controlled cognitive load. The proposed approach can cope with static changes and is robust to video noise. First, we formulate temporal information as symmetrized Rényi divergence, deriving this measure from signal coding theory. Further, we discuss the animated visualization of accelerated video sequences and propose a physiologically motivated blending approach to cope with arbitrary playback velocities. Finally, we compare the proposed method with the current approaches in this field by experiments and a qualitative user study, and show its advantages over motion-based measures.     

On Regression-Based Stopping Times

We study approaches that fit a linear combination of basis functions to the continuation value function of an optimal stopping problem and then employ a greedy policy based on the resulting approximation. We argue that computing weights to maximize expected payoff of the greedy policy or to minimize expected squared-error with respect to an invariant measure is intractable. On the other hand, certain versions of approximate value iteration lead to policies competitive with those that would result from optimizing the latter objective.     

World lines

In this paper we present World Lines as a novel interactive visualization that provides complete control over multiple heterogeneous simulation runs. In many application areas, decisions can only be made by exploring alternative scenarios. The goal of the suggested approach is to support users in this decision making process. In this setting, the data domain is extended to a set of alternative worlds where only one outcome will actually happen. World Lines integrate simulation, visualization and computational steering into a single unified system that is capable of dealing with the extended solution space. World Lines represent simulation runs as causally connected tracks that share a common time axis. This setup enables users to interfere and add new information quickly. A World Line is introduced as a visual combination of user events and their effects in order to present a possible future. To quickly find the most attractive outcome, we suggest World Lines as the governing component in a system of multiple linked views and a simulation component. World Lines employ linking and brushing to enable comparative visual analysis of multiple simulations in linked views. Analysis results can be mapped to various visual variables that World Lines provide in order to highlight the most compelling solutions. To demonstrate this technique we present a flooding scenario and show the usefulness of the integrated approach to support informed decision making.     

Gremlin: an interactive visualization model for analyzing genomic rearrangements

In this work we present, apply, and evaluate a novel, interactive visualization model for comparative analysis of structural variants and rearrangements in human and cancer genomes, with emphasis on data integration and uncertainty visualization. To support both global trend analysis and local feature detection, this model enables explorations continuously scaled from the high-level, complete genome perspective, down to the low-level, structural rearrangement view, while preserving global context at all times. We have implemented these techniques in Gremlin, a genomic rearrangement explorer with multi-scale, linked interactions, which we apply to four human cancer genome data sets for evaluation. Using an insight-based evaluation methodology, we compare Gremlin to Circos, the state-of-the-art in genomic rearrangement visualization, through a small user study with computational biologists working in rearrangement analysis. Results from user study evaluations demonstrate that this visualization model enables more total insights, more insights per minute, and more complex insights than the current state-of-the-art for visual analysis and exploration of genome rearrangements.     

Marine Geospatial Ecology Tools: An integrated framework for ecological geoprocessing with ArcGIS,Python, R,MATLAB, and C++

With the arrival of GPS, satellite remote sensing, and personal computers, the last two decades have witnessed rapid advances in the field of spatially-explicit marine ecological modeling. But with this innovation has come complexity. To keep up, ecologists must master multiple specialized software packages, such as ArcGIS for display and manipulation of geospatial data, R for statistical analysis, and MATLAB for matrix processing. This requires a costly investment of time and energy learning computer programming, a high hurdle for many ecologists. To provide easier access to advanced analytic methods, we developed Marine Geospatial Ecology Tools (MGET), an extensible collection of powerful, easy-to-use, open-source geoprocessing tools that ecologists can invoke from ArcGIS without resorting to computer programming. Internally, MGET integrates Python, R, MATLAB, and C++, bringing the power of these specialized platforms to tool developers without requiring developers to orchestrate the interoperability between them.In this paper, we describe MGET’s software architecture and the tools in the collection. Next, we present an example application: a habitat model for Atlantic spotted dolphin (Stenella frontalis) that predicts dolphin presence using a statistical model fitted with oceanographic predictor variables. We conclude by discussing the lessons we learned engineering a highly integrated tool framework.     

<Emphasis Type="Italic">A Midsummer Night’s Dream</Emphasis> (with flying robots)

Seven flying robot “fairies” joined human actors in the Texas A&;M production of William Shakespeare’s A Midsummer Night’s Dream. The production was a collaboration between the departments of Computer Science and Engineering, Electrical and Computer Engineering, and Theater Arts. The collaboration was motivated by two assertions. First, that the performing arts have principles for creating believable agents that will transfer to robots. Second, the theater is a natural testbed for evaluating the response of untrained human groups (both actors and the audience) to robots interacting with humans in shared spaces, i.e., were believable agents created? The production used two types of unmanned aerial vehicles, an AirRobot 100-b quadrotor platform about the size of a large pizza pan, and six E-flite Blade MCX palm-sized toy helicopters. The robots were used as alter egos for fairies in the play; the robots did not replace any actors, instead they were paired with them. The insertion of robots into the production was not widely advertised so the audience was the typical theatergoing demographic, not one consisting of people solely interested technology. The use of radio-controlled unmanned aerial vehicles provides insights into what types of autonomy are needed to create appropriate affective interactions with untrained human groups. The observations from the four weeks of practice and eight performances contribute (1) a taxonomy and methods for creating affect exchanges between robots and untrained human groups, (2) the importance of improvisation within robot theater, (3) insights into how untrained human groups form expectations about robots, and (4) awareness of the importance of safety and reliability as a design constraint for public engagement with robot platforms. The taxonomy captures that apparent affect can be created without explicit affective behaviors by the robot, but requires talented actors to convey the situation or express reactions. The audience’s response to robot crashes was a function of whether they had the opportunity to observe how the actors reacted to robot crashes on stage, suggesting that pre-existing expectations must be taken into account in the design of autonomy. Furthermore, it appears that the public expect robots to be more reliable (an expectation of consumer product hardening) and safe (an expectation from product liability) than the current capabilities and this may be a major challenge or even legal barrier for introducing robots into shared public spaces. These contributions are expected to inform design strategies for increasing public engagement with robot platforms through affect, and shows the value of arts-based approaches to public encounters with robots both for generating design strategies and for evaluation.     

Evaluating maps produced by urban search and rescue robots: lessons learned from RoboCup

This paper presents the map evaluation methodology developed for the Virtual Robots Rescue competition held as part of RoboCup. The procedure aims to evaluate the quality of maps produced by multi-robot systems with respect to a number of factors, including usability, exploration, annotation and other aspects relevant to robots and first responders. In addition to the design choices, we illustrate practical examples of maps and scores coming from the latest RoboCup contest, outlining strengths and weaknesses of our modus operandi. We also show how a benchmarking methodology developed for a simulation testbed effortlessly and faithfully transfers to maps built by a real robot. A number of conclusions may be derived from the experience reported in this paper and a thorough discussion is offered.     

Robust Cardiac Function Assessment in 4D PC‐MRI Data of the Aorta and Pulmonary Artery

Four‐dimensional phase‐contrast magnetic resonance imaging (4D PC‐MRI) allows the non‐invasive acquisition of time‐resolved, 3D blood flow information. Stroke volumes (SVs) and regurgitation fractions (RFs) are two of the main measures to assess the cardiac function and severity of valvular pathologies. The flow rates in forward and backward direction through a plane above the aortic or pulmonary valve are required for their quantification. Unfortunately, the calculations are highly sensitive towards the plane's angulation since orthogonally passing flow is considered. This often leads to physiologically implausible results. In this work, a robust quantification method is introduced to overcome this problem. Collaborating radiologists and cardiologists were carefully observed while estimating SVs and RFs in various healthy volunteer and patient 4D PC‐MRI data sets with conventional quantification methods, that is, using a single plane above the valve that is freely movable along the centerline. By default it is aligned perpendicular to the vessel's centerline, but free angulation (rotation) is possible. This facilitated the automation of their approach which, in turn, allows to derive statistical information about the plane angulation sensitivity. Moreover, the experts expect a continuous decrease of the blood flow volume along the vessel course. Conventional methods are often unable to produce this behaviour. Thus, we present a procedure to fit a monotonous function that ensures such physiologically plausible results. In addition, this technique was adapted for the usage in branching vessels such as the pulmonary artery. The performed informal evaluation shows the capability of our method to support diagnosis; a parameter evaluation confirms the robustness. Vortex flow was identified as one of the main causes for quantification uncertainties.