Title: Patrolling on Dynamic Ring Networks
Time: 15:50
Location: Acadia Lab, Building Zeta
Type: Research talk
Speaker: Shantanu Das
Abstract:
We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in every I(n) time units, with the objective of minimizing the idle time I(n). While patrolling has been studied previously for static networks, we investigate the problem on dynamic networks with a fixed set of nodes, but dynamic edges. In particular, we consider 1-interval-connected ring networks and provide various patrolling algorithms for such networks, for k = 2 or k > 2 agents. We also show almost matching lower bounds that hold even for the best starting configurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs.
Tag Archives: Robotics
19/09/2019 – Talk by Euripdes Markou
Title: Exploring Graphs with Time Constraints by Unreliable Collections of Mobile Robots
Time: 15:15
Location: Acadia Lab, Building Zeta
Type: Research talk
Speaker: Euripdes Markou
Abstract:
A graph environment must be explored by a collection of mobile robots. Some of the robots, a priori unknown, may turn out to be unreliable. The graph is weighted and each node is assigned a deadline. The exploration is successful if each node of the graph is visited before its deadline by a reliable robot. The edge weight corresponds to the time needed by a robot to traverse the edge. Given the number of robots which may crash, is it possible to design an algorithm, which will always guarantee the exploration, independently of the choice of the subset of unreliable robots by the adversary? We find the optimal time, during which the graph may be explored. Our approach permits to find the maximal number of robots, which may turn out to be unreliable, and the graph is still guaranteed to be explored.
We concentrate on line graphs and rings, for which we give positive results. We start with the case of the collections involving only reliable robots. We give algorithms finding optimal times needed for exploration when the robots are assigned to fixed initial positions as well as when such starting positions may be determined by the algorithm. We extend our consideration to the case when some number of robots may be unreliable. Our most surprising result is that solving the line exploration problem with robots at given positions, which may involve crash-faulty ones, is NP-hard. The same problem has polynomial solutions for a ring and for the case when the initial robots’ positions on the line are arbitrary. The exploration problem is shown to be NP-hard for star graphs, even when the team consists of only two reliable robots.
13/12/2018 – Talk by Shantanu Das
Title: Exploration Algorithms for Energy Constrained Robots
Time: 13:00
Location: Meeting Room B, Building Zeta
Type: Research talk
Speaker: Shantanu Das
Abstract:
We consider a team of mobile robots moving on graph where each robot has a constraint on its energy consumption which limits the number of edges it can traverse. Under this constraint we look at the problem of graph exploration. Since any single robot may not completely explore the graph, the robots need to collaborate so that each node is visited by some robot. We consider three different optimization criteria: the size of the team, the energy budget per robot, and finally the number of nodes visited. We present efficient algorithms and prove lower bounds on these different measures of optimization. We also show a separation result between exploration with return and exploration without return.
10/10/2018 – Talk by Gianluca Caiazza
Title: Supporting security of robotic software: access control policies and immutablezation of log records
Time: 14:30
Location: Meeting Room B, Building Zeta
Type: Research talk
Speaker: Gianluca Caiazza
Abstract: Security of robotics systems, as well as of the related middleware infrastructures, is a critical issue for industrial and domestic IoT applications, and it needs to be continuously assessed throughout the whole development lifecycle. Furthermore, logging is crucial in robotics research, providing prolonged insights into a robot’s situational understanding, progression of behavioral state, and resulting outcomes. Such recordings are invaluable when debugging complex robotic applications or profiling experiments ex post facto. The next generation open source robotic software stack, ROS2, is now targeting support for Secure DDS, providing the community with valuable tools for secure real world robotic deployments. However, given the growing number of high profile public incidents involving self-driving automotives, resulting in fatality or regulatory policy making, it is paramount that the integrity, authenticity and non-repudiation of such system logs are maintained to ensure accountability. Being mobile cyberphysical systems, robots present new threats and vulnerabilities beyond traditional IT: unsupervised physical system access or postmortem collusion between robot and OEM could result in the truncation or alteration of prior records. In this seminar, we discuss a framework for procedural provisioning access control policies for robotic software, as well as for verifying the compliance of generated transport artifacts and decision point implementations. Moreover, we address immutablezation of log records via integrity proofs and distributed ledgers with special consideration for mobile and public service robot deployments.
Alert: the seminar has been rescheduled from 13:30 to 14:30
