搜索结果：Cups

In the cup game, an adversary distributes 1 unit of water among $n$ cups every time step. The player then selects a single cup from which to remove 1 unit of water. In the bamboo trimming problem, the adversary must choose fixed rates for the cups, and the player is additionally allowed to empty the chosen cup entirely. Past work has shown that the optimal backlog in these two settings is $Θ(\log n)$ and 2 respectively. The greedy algorithm has been shown in previous work to be exactly optimal in the general cup game and asymptotically optimal in the bamboo setting. The greedy algorithm has been conjectured [16] to achieve the exactly optimal backlog of 2 in the bamboo setting as well. In this paper, we prove a lower bound of $2.076$ for the backlog of the greedy algorithm, disproving the conjecture of [16]. We also introduce a new algorithm, a hybrid greedy/Deadline-Driven, which achieves backlog $O(\log n)$ in the general cup game, and remains exactly optimal for the bamboo trimming problem and the fixed-rate cup game -- this constitutes the first algorithm that achieves asymptotically optimal performance across all three settings. Additionally, we introduce a new model, the semi

The group stage of a sports tournament is often made more appealing by introducing additional constraints in the group draw that promote an attractive and balanced group composition. For example, the number of intra-regional group matches is minimised in several World Cups. However, under such constraints, the traditional draw procedure may become non-uniform, meaning that the feasible allocations of the teams into groups are not equally likely to occur. Our paper quantifies this non-uniformity of the 2026 FIFA World Cup draw for the official draw procedure, as well as for 47 reasonable alternatives implied by all permutations of the four pots and two group labelling policies. We show why simulating with a recursive backtracking algorithm is intractable, and propose a workable implementation using integer programming. The official draw mechanism is found to be optimal based on four measures of non-uniformity. Nonetheless, non-uniformity can be more than halved if the organiser aims to treat the best teams drawn from the first pot equally.

We determine conditions on classical group algebra codes so that they have pre-orientation for cup products and copy-cup gates. This defines quantum codes that have constant-depth $\operatorname{CZ}$ and $\operatorname{CCZ}$ gates constructed via tensor products of classical group algebra codes, including hypergraph and balanced products. We show that determining the conditions relies on solving the perfect matching problem in graph theory. Conditions are fully determined for the 2- and 3-copy-cup gates, for group algebra codes up to weight 4, including for codes with odd check weight. These include the bivariate bicycle codes, which we show do not have the pre-orientation for either type of copy-cup gate. We show that abelian weight 4 group algebra codes satisfying the non-associative 3-copy-cup gate necessarily have a code distance of 2, whereas codes that satisfy conditions for the symmetric 3-copy-cup gate can have higher distances, and in fact also satisfy conditions for the 2-copy-cup gate. Finally we find examples of quantum codes from the product of abelian group algebra codes that have inter-code constant-depth $\operatorname{CZ}$ and $\operatorname{CCZ}$ gates.

Multiple-suction-cup grasping can improve the efficiency of bin picking in cluttered scenes. In this paper, we propose a grasp planner for a vacuum gripper to use multiple suction cups to simultaneously grasp multiple objects or an object with a large surface. To take on the challenge of determining where to grasp and which cups to activate when grasping, we used 3D convolution to convolve the affordable areas inferred by neural network with the gripper kernel in order to find graspable positions of sampled gripper orientations. The kernel used for 3D convolution in this work was encoded including cup ID information, which helps to directly determine which cups to activate by decoding the convolution results. Furthermore, a sorting algorithm is proposed to find the optimal grasp among the candidates. Our planner exhibited good generality and successfully found multiple-cup grasps in previous affordance map datasets. Our planner also exhibited improved picking efficiency using multiple suction cups in physical robot picking experiments. Compared with single-object (single-cup) grasping, multiple-cup grasping contributed to 1.45x, 1.65x, and 1.16x increases in efficiency for picking

Multi-suction-cup grippers are frequently employed to perform pick-and-place robotic tasks, especially in industrial settings where grasping a wide range of light to heavy objects in limited amounts of time is a common requirement. However, most existing works focus on using one or two suction cups to grasp only irregularly shaped but light objects. There is a lack of research on robust manipulation of heavy objects using larger arrays of suction cups, which introduces challenges in modeling and predicting grasp failure. This paper presents a general approach to modeling grasp strength in multi-suction-cup grippers, introducing new constraints usable for trajectory planning and optimization to achieve fast and reliable pick-and-place maneuvers. The primary modeling challenge is the accurate prediction of the distribution of loads at each suction cup while grasping objects. To solve for this load distribution, we find minimum spring potential energy configurations through a simple quadratic program. This results in a computationally efficient analytical solution that can be integrated to formulate grasp failure constraints in time-optimal trajectory planning. Finally, we present exp

Fay, Hurlbert and Tennant recently introduced a one-player game on a finite connected graph $G$, which they called cup stacking. Stacks of cups are placed at the vertices of $G$, and are transferred between vertices via stacking moves, subject to certain constraints, with the goal of stacking all cups at a single target vertex. If this is possible for every target vertex of $G$, then $G$ is called stackable. In this paper, we prove that if $G$ admits a Hamilton path, then $G$ is stackable, which confirms several of the conjectures raised by Fay, Hurlbert and Tennant. Furthermore, we prove stackability for certain powers of bipartite graphs, and we construct graphs of arbitrarily large minimum degree and connectivity that do not allow stacking onto any of their vertices.

Here we introduce a new game on graphs, called cup stacking, following a line of what can be considered as $0$-, $1$-, or $2$-person games such as chip firing, percolation, graph burning, zero forcing, cops and robbers, graph pebbling, and graph pegging, among others. It can be more general, but the most basic scenario begins with a single cup on each vertex of a graph. (This simplification coincides with an earlier game devised by Gordon Hamilton.) For a vertex with $k$ cups on it we can move all its cups to a vertex at distance $k$ from it, provided the second vertex already has at least one cup on it. The object is to stack all cups onto some pre-described target vertex. We say that a graph is stackable if this can be accomplished for all possible target vertices. In this paper we study cup stacking on many families of graphs, developing a characterization of stackability in graphs and using it to prove the stackability of complete graphs, paths, cycles, grids, the Petersen graph, many Kneser graphs, some trees, cubes of dimension up to 20, "somewhat balanced" complete $t$-partite graphs, and Hamiltonian diameter two graphs. Additionally we use the Gallai-Edmonds Structure Theor

Conventional suction cups lack sensing capabilities for contact-aware manipulation in unstructured environments. This paper presents FlexiCup, a multimodal suction cup with wireless electronics that integrate dual-zone vision-tactile sensing. The central zone dynamically switches between vision and tactile modalities via illumination control, while the peripheral zone provides continuous spatial awareness. The modular mechanical design supports both vacuum (sustained-contact adhesion) and Bernoulli (contactless lifting) actuation while maintaining the identical dual-zone sensing architecture, demonstrating sensing-actuation decoupling where sensing and actuation principles are orthogonally separable. We validate hardware versatility through dual control paradigms. Modular perception-driven grasping achieves comparable success rates across vacuum (90.0%) and Bernoulli (86.7%) modes using identical sensing and control pipelines, validating the sensing architecture's effectiveness across fundamentally different pneumatic principles. Diffusion-based end-to-end learning achieves 73.3% and 66.7% success on contact-aware manipulation tasks, with ablation studies confirming 13% improvement

Suction cups are an important gripper type in industrial robot applications, and prior literature focuses on using vision-based planners to improve grasping success in these tasks. Vision-based planners can fail due to adversarial objects or lose generalizability for unseen scenarios, without retraining learned algorithms. We propose haptic exploration to improve suction cup grasping when visual grasp planners fail. We present the Smart Suction Cup, an end-effector that utilizes internal flow measurements for tactile sensing. We show that model-based haptic search methods, guided by these flow measurements, improve grasping success by up to 2.5x as compared with using only a vision planner during a bin-picking task. In characterizing the Smart Suction Cup on both geometric edges and curves, we find that flow rate can accurately predict the ideal motion direction even with large postural errors. The Smart Suction Cup includes no electronics on the cup itself, such that the design is easy to fabricate and haptic exploration does not damage the sensor. This work motivates the use of suction cups with autonomous haptic search capabilities in especially adversarial scenarios.

Perching on {the surface} of moving objects, like vehicles, could extend the flight {time} and range of quadrotors. Suction cups are usually adopted for {surface attachment} due to their durability and large adhesive force. To seal on {a surfaces}, suction cups {must} be aligned with {the surface} and {possess proper relative tangential velocity}. {However, quadrotors' attitude and relative velocity errors would become significant when the object surface is moving and inclined. To address this problem, we proposed a real-time trajectory planning algorithm. The time-optimal aggressive trajectory is efficiently generated through multimodal search in a dynamic time-domain. The velocity errors relative to the moving surface are alleviated.} To further adapt to the residual errors, we design a compliant gripper using self-sealing cups. Multiple cups in different directions are integrated into a wheel-like mechanism to increase the tolerance to attitude errors. The wheel mechanism also eliminates the requirement of matching the attitude and tangential velocity. {Extensive tests are conducted to perch on static and moving surfaces at various inclinations.} Results demonstrate that our pro

We denote a path on $t$ vertices as $P_t$ and a cycle on $t$ vertices as $C_t$. For two vertex-disjoint graphs $G_1$ and $G_2$, the {\em union} $G_1\cup G_2$ is the graph with $V(G_1\cup G_2)=V(G_1)\cup V(G_2)$ and $E(G_1\cup G_2)=E(G_1)\cup E(G_2)$. A {\em diamond} (resp. {\em gem}) is a graph consisting of a $P_3$ (resp. $P_4$) and a new vertex adjacent to all vertices of the $P_3$ (resp. $P_4$), and a {\em butterfly} is a graph consisting of two triangles that share one vertex. In this paper, we show that $χ(G)\le 3ω(G)-2$ if $G$ is a ($P_2\cup P_4$, gem)-free graph, $χ(G)\le \frac{ω(G)^2+3ω(G)-2}{2}$ if $G$ is a ($P_2\cup P_4$, butterfly)-free graph. We also study the class of ($P_2\cup P_4$, diamond)-free graphs, and show that, for such a graph $G$, $χ(G)\leq4$ if $ω(G)=2$, $χ(G)\leq7$ if $ω(G)=3$, $χ(G)\leq9$ if $ω(G)=4$, and $χ(G)\leq2ω(G)-1$ if $ω(G)\ge 5$. Moreover, we prove that $G$ is perfect if $G$ is ($P_2\cup P_4$, diamond, $C_5$)-free with $ω(G)\geq5$.