Most consumer-level low-cost unmanned aerial vehicles (UAVs) have limited battery power and long charging time. Due to these energy constraints, they cannot accomplish many practical tasks, such as monitoring a sport or political event for hours. The
problem of providing the service to cover an area for an extended time is known as persistent covering in the literature. In the past, researchers have proposed various hardware platforms, such as battery-swapping mechanisms, to provide persistent covering. However, algorithmic approaches are limited mostly due to the computational complexity and intractability of the problem. Approximation algorithms have been considered to segment a large area into smaller cells that require periodic visits under the latency constraints. However, these methods assume unlimited energy. In this paper, we explore geometric and topological properties that allow us to significantly reduce the size of the optimization problem. Consequently, the proposed method can efficiently determine the minimum number of UAVs needed and schedule their routes to cover an area persistently. We demonstrated experimentally that the proposed algorithm has better performance than the baseline methods.
When the human-robot interactions become ubiquitous, the environment surrounding these interactions will have significant impact on the safety and comfort of the human and the effectiveness and efficiency of the robot. Although most robots are design
ed to work in the spaces created for humans, many environments, such as living rooms and offices, can be and should be redesigned to enhance and improve human-robot collaboration and interactions. This work uses autonomous wheelchair as an example and investigates the computational design in the human-robot coexistence spaces. Given the room size and the objects $O$ in the room, the proposed framework computes the optimal layouts of $O$ that satisfy both human preferences and navigation constraints of the wheelchair. The key enabling technique is a motion planner that can efficiently evaluate hundreds of similar motion planning problems. Our implementation shows that the proposed framework can produce a design around three to five minutes on average comparing to 10 to 20 minutes without the proposed motion planner. Our results also show that the proposed method produces reasonable designs even for tight spaces and for users with different preferences.
This paper presents the first purely numerical (i.e., non-algebraic) subdivision algorithm for the isotopic approximation of a simple arrangement of curves. The arrangement is simple in the sense that any three curves have no common intersection, any
two curves intersect transversally, and each curve is non-singular. A curve is given as the zero set of an analytic function $f:mathbb{R}^2rightarrow mathbb{R}^2$, and effective interval forms of $f, frac{partial{f}}{partial{x}}, frac{partial{f}}{partial{y}}$ are available. Our solution generalizes the isotopic curve approximation algorithms of Plantinga-Vegter (2004) and Lin-Yap (2009). We use certified numerical primitives based on interval methods. Such algorithms have many favorable properties: they are practical, easy to implement, suffer no implementation gaps, integrate topological with geometric computation, and have adaptive as well as local complexity. A version of this paper without the appendices appeared in Lien et al. (2014).
Robotic shepherding problem considers the control and navigation of a group of coherent agents (e.g., a flock of bird or a fleet of drones) through the motion of an external robot, called shepherd. Machine learning based methods have successfully sol
ved this problem in an empty environment with no obstacles. Rule-based methods, on the other hand, can handle more complex scenarios in which environments are cluttered with obstacles and allow multiple shepherds to work collaboratively. However, these rule-based methods are fragile due to the difficulty in defining a comprehensive set of rules that can handle all possible cases. To overcome these limitations, we propose the first known learning-based method that can herd agents amongst obstacles. By using deep reinforcement learning techniques combined with the probabilistic roadmaps, we train a shepherding model using noisy but controlled environmental and behavioral parameters. Our experimental results show that the proposed method is robust, namely, it is insensitive to the uncertainties originated from both environmental and behavioral models. Consequently, the proposed method has a higher success rate, shorter completion time and path length than the rule-based behavioral methods have. These advantages are particularly prominent in more challenging scenarios involving more difficult groups and strenuous passages.
In digital painting software, layers organize paintings. However, layers are not explicitly represented, transmitted, or published with the final digital painting. We propose a technique to decompose a digital painting into layers. In our decompositi
on, each layer represents a coat of paint of a single paint color applied with varying opacity throughout the image. Our decomposition is based on the paintings RGB-space geometry. In RGB-space, a geometric structure is revealed due to the linear nature of the standard Porter-Duff over pixel compositing operation. The vertices of the convex hull of pixels in RGB-space suggest paint colors. Users choose the degree of simplification to perform on the convex hull, as well as a layer order for the colors. We solve a constrained optimization problem to find maximally translucent, spatially coherent opacity for each layer, such that the composition of the layers reproduces the original image. We demonstrate the utility of the resulting decompositions for re-editing.
