Reconstruction and Simplification of Surfaces from Contours

In this paper we consider the problem of reconstructing triangular surfaces from given contours. An algorithm solving this problem must decide which contours of two successive slices should be connected by the surface (branching problem) and, given that, which vertices of the assigned contours should be connected for the triangular mesh (correspondence problem). We present a new approach that solves both tasks in an elegant way. The main idea is to employ discrete distance fields enhanced with correspondence information. This allows us not only to connect vertices from successive slices in a reasonable way but also to solve the branching problem by creating intermediate contours where adjacent contours differ too much. Last but not least we show how the 2D distance fields used in the reconstruction step can be converted to a 3D distance field that can be advantageously exploited for distance calculations during a subsequent simplification step.     

Recurrent Neural Network to Forecast Sprint Performance

ABSTRACT

The present paper demonstrates that the performance of an elite track and field sprinter can be predicted by means of the dynamic, nonlinear mathematical method of recurrent neural networks (RNNs). Dataset considers three years of National Collegiate Athletics Association (NCAA) Division I competitions where the student-athlete recorded heart rate variability two days precedent to each competition. Input parameters were selected by transfer entropy via permutation tests. Subsequently, two RNN topologies, Elman and Jordan, were trained with 32 competitions, validated with 7 competitions, and tested against 6 held-out competitions. Resultant RNNs, which possess a sense of time and memory, were able to learn time-dependent sequence of acute adaptation and predict race times with an error of 0.09–0.16 s on held-out test data. Root mean sum of differences of successive R-R intervals (RMSSD), an indicator of parasympathetic tone, and direct current biopotentials, indicator of active wakefulness, were most predictive toward competitive performance for an NCAA Division I male sprinter.     

Three years of the RoboCup standard platform league drop-in player competition

The Standard Platform League is one of the main competitions at the annual RoboCup world championships. In this competition, teams of five humanoid robots play soccer against each other. In 2013, the league began a new competition which serves as a testbed for cooperation without pre-coordination: the Drop-in Player Competition. Instead of homogeneous robot teams that are each programmed by the same people and hence implicitly pre-coordinated, this competition features ad hoc teams, i.e. teams that consist of robots originating from different RoboCup teams and as such running different software. In this article, we provide an overview of this competition, including its motivation, rules, and how these rules have changed across three iterations of the competition. We then present and analyze the strategies utilized by various drop-in players as well as the results of the first three competitions before suggesting improvements for future competitive evaluations of ad hoc teamwork. To the best of our knowledge, these three competitions are the largest annual ad hoc teamwork robotic experiment to date. Across three years, the competition has seen 56 entries from 30 different organizations and consisted of 510 min of game time that resulted in approximately 85 robot hours.     

Writer identification using oriented Basic Image Features and the Delta encoding

We describe how oriented Basic Image Feature Columns (oBIF Columns) can be used for writer identification and how this texture-based scheme can be enhanced by encoding a writer's style as the deviation from the mean encoding for a population of writers. We hypothesise that this deviation, the Delta encoding, provides a more informative encoding than the texture-based encoding alone. The methods have been evaluated using the IAM dataset and by making entries to two top international competitions for assessing the state-of-the-art in writer identification. We demonstrate that the oBIF Column scheme on its own is sufficient to gain a performance level of 99% when tested using 300 writers from the IAM dataset. However, on the more challenging competition datasets, significantly improved performance was obtained using the Delta encoding scheme, which achieved first place in both competitions. In our characterisation of the Delta encoding, we demonstrate that the method is making use of information contained in the correlation between the written style of different textual elements, which may not be used by other methods.     

Performance Competitions as Research Infrastructure: Large Scale Comparative Studies of Multi-Agent Teams

Performance competitions (events that pit many different programs against each other on a standardized task) provide a way for a research community to promote research progress towards challenging goals. In this paper, we argue that for maximum research benefit, any such competition must involve comparative studies under closely controlled, varying conditions. We demonstrate the critical role of comparative studies in the context of one well-known and growing performance competition: the annual Robotic Soccer World Cup (RoboCup) Championship. Specifically, over the past three years, we have carried out annual large-scale comparative evaluations—distinct from the competition itself—of the multi-agent teams taking part in the largest RoboCup league. Our study, which involved 30 different teams of agents produced by dozens of different research groups, focused on robustness. We show that (i) multi-agent teams exhibit a clear performance-robustness tradeoff; (ii) teams tend to over-specialize, so that they cannot handle beneficial changes we make to their operating environment; and (iii) teams improve in performance more than in robustness from one year to the next, despite the emphasis by RoboCup organizers on robustness as a key challenge. These results demonstrate the potential of large-scale comparative studies for producing important results otherwise difficult to discover, and are significant both in the lessons they raise for designers of multi-agent teams, and in understanding the place of performance competitions within the multi-agent research infrastructure.     

On scheduling dag s for volatile computing platforms: Area-maximizing schedules

Many modern computing platforms—notably clouds and desktop grids—exhibit dynamic heterogeneity: the availability and computing power of their constituent resources can change unexpectedly and dynamically, even in the midst of a computation. We introduce a new quality metric, area, for schedules that execute computations having interdependent constituent chores (jobs, tasks, etc.) on such platforms. Area measures the average number of tasks that a schedule renders eligible for execution at each step of a computation. Even though the definition of area does not mention and properties of host platforms (such as volatility), intuition suggests that rendering tasks eligible at a faster rate will have a benign impact on the performance of volatile platforms—and we report on simulation experiments that support this intuition. We derive the basic properties of the area metric and show how to efficiently craft area-maximizing (A-M) schedules for several classes of significant computations. Simulations that compare A-M scheduling against heuristics ranging from lightweight ones (e.g., FIFO) to computationally intensive ones suggest that A-M schedules complete computations on volatile heterogeneous platforms faster than their competition, by percentages that vary with computation structure and platform behavior—but are often in the double digits.     

Cooperative control through objective achievement

Cooperative control is a key issue for multirobot systems in many practical applications. In this paper, we address the problem of coordinating a set of mobile robots in the RoboCup soccer middle-size league. We show how the coordination problem that we face can be cast as a specific coalition formation problem, and we propose a distributed algorithm to efficiently solve it. Our approach is based on the distributed computation of a measure of satisfaction (called Agent Satisfaction) that each agent computes for each task. We detail how each agent computes the Agent Satisfaction by acquiring sensor perceptions through an omnidirectional vision system, extracting aggregated information from the acquired perception, and integrating such information with that communicated by the teammates. We empirically validate our approach in a simulated scenario and within RoboCup competitions. The experiments in the simulated scenario allow us to analyse the behaviour of the algorithm in different situations, while the use of the algorithm in real competitions validates the applicability of our approach to robotic platforms involved in a dynamic and complex scenario.     

Vision-guided mobile robots for design competitions

We present the Teaching system integration in engineering curricula at universities via popular and effective robot-design competitions. In this article, we first present the robot kit we use and discuss the experiences we gained in, and shortcomings of, our robot competitions. We then present the low-cost color vision system, developed especially for our course. We also discuss our experiences in the 1998 competition, where we first made use of the system, and the 2001 competition. Finally, we present the results of a questionnaire given to students who have completed the course.     

TOOLympics II: competitions on formal methods

This is the second issue in the new “Competitions and Challenges” (CoCha) theme of the International Journal on Software Tools for Technology Transfer. The new theme was established to support competitions and challenges with an appropriate publication venue. The first issue presented the competition on software testing Test-Comp 2019, which was part of the TOOLympics 2019 event. In this second issue for TOOLympics, we present selected competition reports. The TOOLympics event took place as part of the 25-years celebration of the conference TACAS. The goal of the event was to provide an overview of competitions and challenges in the area of formal methods.

     

Bundling and product strategy in channel competition

We investigate the bundling and product strategy in a two‐stage supply chain with the channel competition, and analyze the effect of the bundling strategy on the behavior of supply chain members. In this paper, we consider two situations of channel competitions that are from the external or internal of the supply chain, two types of selling strategies (bundling or unbundling), and two types of product strategies (low or high quality). We propose the game models for different competition situations with the bundling strategy and product‐quality strategy to obtain the optimal decisions for supply chain members. We find that the bundling is the retailer's preferred strategy in two channel competitions; the bundling strategy encourages the competitor (i.e., the new supplier of complementary component) outside the supply chain to provide the low‐quality components, while the product strategy of the channel competitor (i.e., the existing supplier of complementary component) in the supply chain is not affected by the bundling strategy.     

A constraint programming approach to the multiple-venue,sport-scheduling problem

In this paper, we consider the problem of scheduling sports competitions over several venues which are not associated with any of the competitors. A two-phase, constraint programming approach is developed, first identifying a solution that designates the participants and schedules each of the competitions, then assigning each competitor as the “home” or the “away” team. Computational experiments are conducted and the results are compared with an integer goal programming approach. The constraint programming approach achieves optimal solutions for problems with up to sixteen teams, and near-optimal solutions for problems with up to thirty teams.     

Medical data mining: insights from winning two competitions

Two major data mining competitions in 2008 presented challenges in medical domains: KDD Cup 2008, which concerned cancer detection from mammography data; and Informs Data Mining Challenge 2008, dealing with diagnosis of pneumonia based on patient information from hospital files. Our team won both of these competitions, and in this paper we share our lessons learned and insights. We emphasize the aspects that pertain to the general practice and methodology of medical data mining, rather than to the specifics of each modeling competition. We concentrate on three topics: information leakage, its effect on competitions and proof-of-concept projects; consideration of real-life model performance measures in model construction and evaluation; and relational learning approaches to medical data mining tasks.     

VerifyThis 2019: a program verification competition

VerifyThis is a series of program verification competitions that emphasize the human aspect: participants tackle the verification of detailed behavioral properties—something that lies beyond the capabilities of fully automatic verification and requires instead human expertise to suitably encode programs, specifications, and invariants. This paper describes the 8th edition of VerifyThis, which took place at ETAPS 2019 in Prague. Thirteen teams entered the competition, which consisted of three verification challenges and spanned 2 days of work. This report analyzes how the participating teams fared on these challenges, reflects on what makes a verification challenge more or less suitable for the typical VerifyThis participants, and outlines the difficulties of comparing the work of teams using wildly different verification approaches in a competition focused on the human aspect.

     

TOOLympics I: Competition on software testing

Research competitions and challenges are a driving force in transferring theoretical results into working software tools that demonstrate the state of the art in the respective field of research. Regular comparative evaluations provide guidance to practitioners that have to select new technology and tools for their development process. In order to support competitions and challenges with an appropriate publication venue, a new theme of issues in the International Journal on Software Tools for Technology Transfer was created. This issue is the inaugural issue of the newly introduced theme on “Competitions and Challenges” (CoCha). Test-Comp, the International Competition on Software Testing, is an example of a tool competition, where the research teams submit tools for test-generation, and the competition evaluates the tools and assigns scores according to achieved coverage. Test-Comp 2019 was part of the TOOLympics event, which took place as part of the 25-year celebration of the conference TACAS. Thus, it is most natural to start the new STTT-CoCha theme with a special issue that describes the results and participating systems of Test-Comp 2019. There will be a second issue on TOOLympics with contributions from other competitions.

     

Design and implementation of domain-specific language easytime

Measuring time in mass sporting competitions is, typically, performed with a timing system that consists of a measuring technology and a computer system. The first is dedicated to tracking events that are triggered by competitors and registered by measuring devices (primarily based on RFID technology). The latter enables the processing of these events. In this paper, the processing of events is performed by an agent that is controlled by the domain-specific language, EasyTime. EasyTime improves the flexibility of the timing system because it supports the measuring of time in various sporting competitions, their quick adaptation to the demands of new sporting competitions and a reduction in the number of measuring devices. Essentially, we are focused on the development of a domain specific language. In practice, we made two case studies of using EasyTime by measuring time in two different sporting competitions. The use of EasyTime showed that it can be useful for sports clubs and competition organizers by aiding in the results of smaller sporting competitions, while in larger sporting competitions it could simplify the configuration of the timing system.     

Scheduling Time-Constrained Communication in Linear Networks

Abstract. We study the problem of centrally scheduling multiple messages in a linear network, when each message has both a release time and a deadline. We show that the problem of transmitting optimally many messages is NP-Hard, both when messages may be buffered in transit and when they may not be. For either case, we present efficient algorithms that produce approximately optimal schedules. In particular, our bufferless scheduling algorithm achieves throughput that is within a factor of 2 of optimal. We show that buffering can improve throughput in general by a logarithmic factor (but no more), but that in several significant special cases, such as when all messages can be released immediately, buffering can help by only a small constant factor. Finally, we show how to convert any of our centralized, offline bufferless schedules to a fully distributed online buffered schedule of equal throughput. Most of our results extend readily to ring-structured networks.     

Solving scheduling problems by untimed model checking

In this article, we show how scheduling problems can be modelled in untimed process algebra, by using special tick actions. A minimal-cost trace leading to a particular action, is one that minimises the number of tick steps. As a result, we can use any (timed or untimed) model checking tool to find shortest schedules. Instantiating this scheme to μCRL, we profit from a richer specification language than timed model checkers usually offer. Also, we can profit from efficient distributed state space generators. We propose a variant of breadth-first search that visits all states between consecutive tick steps, before moving to the next time slice. We experimented with a sequential and a distributed implementation of this algorithm. In addition, we experimented with beam search, which visits only parts of the search space, to find near-optimal solutions. Our approach is applied to find optimal schedules for test batches of a realistic clinical chemical analyser, which performs several kinds of tests on patient samples.     

Short-term harvest planning including scheduling of harvest crews

The problem we consider is short‐term harvesting planning for a total planning period of 4–6 weeks where we want to decide the harvest sequences or schedules for harvest crews. A schedule is an order or sequence of harvest areas assigned to each crew. The harvesting of areas is planned in order to meet industrial demand. The total cost includes harvesting, transportation, and storage. One considerable cost is due to the quality reduction of logs stored at harvest areas. There are a number of restrictions to be considered. Areas are of varying size and the composition of assortments in each area is different. Each harvest team has different skills, a different home base, and different production capacity. Another aspect is the road network. There is a cost related to road opening (restoring, snow removal). In this paper, we develop a mixed integer programming (MIP) model for the problem. The schedules are represented by 0/1 variables. With a limited number of schedules, the problem can be solved by a commercial MIP solver. We have also developed a heuristic solution approach that provides high‐quality integer solutions within a distinct time limit to be used when more schedules are used. Computational results from a major Swedish forest company are presented.