Copyright: © Kurt Beyer

Security

Probabilistic models are not only a formidable tool when dealing with uncertainty and incomplete information, but they sometimes are a necessity rather than an option. This holds in particular for security. Public key encryption schemes cannot be secure without being probabilistic. Many security notions such as semantic security of an encryption scheme are inherently probabilistic, and key generation for symmetric and asymmetric cryptographic algorithms requires strong random number generators. In this Research Training Group, we will study randomization in two highly active research topics: secure multi-party computation and security in wireless mesh networks. In secure multi-party computation, a number of parties aim to jointly compute a function in a distributed fashion such that no party learns more about the other parties’ private inputs than what can be inferred by the function’s output and the party’s own private inputs. The study of such protocols under probabilistic attacker models such as the covert adversary model is of particular interest. In this setting the trade-off between security and algorithmic efficiency and quality of the result of a protocol is of particular interest. Accounting is another pressing problem in security. In many cases, the centralized provision of a generally useful service attracts unwanted attention to the provider who is forced to justify the provision of the service and its attendant costs. One way that the unwanted attention can be avoided is to distribute the costs among the community that benefits and then subsidize or reimburse that community. Security aspects play an important role in distributed accounting as, for example, the payments made by individual sides need to be invisible for others and manipulation of accounting data has to be detected. A novel trend in distributed accounting - in particular for wireless networks - is to exploit probabilistic protocols.

Uncertainty in Robotics

From the early beginning, uncertainty in data has played a very important role in robotics, as most actuators and sensors in autonomous robots are noisy. For example, RGB-D sensors like the Microsoft Kinect, which provides both colour images and depth information, are routinely used for object recognition, but the interpretation of the coarse-grained 3D point clouds returned by the sensor is inherently uncertain. In order to cope with noisy sensors and actuators, probabilistic methods have been developed for both low-level control such as navigation routines and high-level task planning. Prominent examples are particle filter-based methods for simultaneous localization and mapping, and partially observable Markov decision processes, for high-level planning and decision making. A challenge is to integrate symbolic reasoning techniques with reasoning about uncertainty in order to arrive, among other things, at more powerful methods for planning and robot program verification. Another important research direction concerns the coordination of multiple robots, both in cooperative and antagonistic settings. Decision making under uncertainty in such settings has been addressed, most notably using decentralized POMDPs, but as in the case of regular POMDPs the formalism is limited in expressiveness. Another challenge is verifying temporal properties of logic-based robot programs - expressive robot programming languages like Golog easily render the verification problem undecidable if no restrictions are imposed.

Railway Engineering

Railway operations research deals with re-scheduling, and dispatching operational management as well as with dimensioning and design of railway networks. Due to a long life-cycle in the rail sector, a careful planning and design of the network as well as a fine-tuned railway service are important challenges. For long-term dimensioning, analytic queueing models are used to obtain capacity results. As the forecast periods are long, models and input data include various uncertainties. Capacities are determined for isolated sections modelled as single-server systems or multi-channel systems. For train scheduling, operational schedules can automatically be generated and evaluated for parts of the network. To warrant robustness against random delays, dispatching actions are used to minimize knock-on delays. A trend is the use of algorithms for automatic dispatching. An important research challenge is incapacity planning using robust optimization. Queueing models used for capacity planning suffer from several limitations. Restrictions have to be imposed on their structure to warrant analytical tractability, scalability is limited, dimensioning is based on full reliability of the infrastructure and rolling stock, and fall-back routes are mostly ignored. Another challenge is in scheduling and dispatching under uncertainty. During the scheduling process the impact of planned long-term and unplanned - sometimes uncertain - short-term construction works has to be considered. Enhanced planning processes will lead to an improved operation yielding less delays. It should be analysed whether structures can be simplified by applying methods from computer science. Additionally the dispatching algorithms should consider the uncertainties within the framework. Finally, CS methods seem promising to boost the safety analysis of railway systems - an extremely important subject in railway engineering.