Reachability-Based Confidence-Aware Probabilistic Collision Detection in Highway Driving

Risk assessment is a crucial component of collision warning and avoidance systems for intelligent vehicles.Reachability-based formal approaches have been developed to ensure driving safety to accurately detect potential vehicle collisions.However,they suffer from over-conservatism,potentially resulting in false–positive risk events in complicated real-world applications.In this paper,we combine two reachability analysis techniques,a backward reachable set(BRS)and a stochastic forward reachable set(FRS),and propose an integrated probabilistic collision–detection framework for highway driving.Within this framework,we can first use a BRS to formally check whether a two-vehicle interaction is safe;otherwise,a prediction-based stochastic FRS is employed to estimate the collision probability at each future time step.Thus,the framework can not only identify non-risky events with guaranteed safety but also provide accurate collision risk estimation in safety-critical events.To construct the stochastic FRS,we develop a neural network-based acceleration model for surrounding vehicles and further incorporate a confidence-aware dynamic belief to improve the prediction accuracy.Extensive experiments were conducted to validate the performance of the acceleration prediction model based on naturalistic highway driving data.The efficiency and effectiveness of the framework with infused confidence beliefs were tested in both naturalistic and simulated highway scenarios.The proposed risk assessment framework is promising for real-world applications.

A self-organization formation configuration based assignment probability and collision detection

The formation control of multiple unmanned aerial vehicles(multi-UAVs)has always been a research hotspot.Based on the straight line trajectory,a multi-UAVs target point assignment algorithm based on the assignment probability is proposed to achieve the shortest overall formation path of multi-UAVs with low complexity and reduce the energy consumption.In order to avoid the collision between UAVs in the formation process,the concept of safety ball is introduced,and the collision detection based on continuous motion of two time slots and the lane occupation detection after motion is proposed to avoid collision between UAVs.Based on the idea of game theory,a method of UAV motion form setting based on the maximization of interests is proposed,including the maximization of self-interest and the maximization of formation interest is proposed,so that multi-UAVs can complete the formation task quickly and reasonably with the linear trajectory assigned in advance.Finally,through simulation verification,the multi-UAVs target assignment algorithm based on the assignment probability proposed in this paper can effectively reduce the total path length,and the UAV motion selection method based on the maximization interests can effectively complete the task formation.

Collision detection of virtual plant based on bounding volume hierarchy: A case study on virtual wheat

Visualization of simulated crop growth and development is of significant interest to crop research and production. This study aims to address the phenomenon of organs cross-drawing by developing a method of collision detection for improving vivid 3D visualizations of virtual wheat crops. First, the triangular data of leaves are generated with the tessellation of non-uniform rational B-splines surfaces. Second, the bounding volumes（BVs） and bounding volume hierarchies（BVHs） of leaves are constructed based on the leaf morphological characteristics and the collision detection of two leaves are performed using the Separating Axis Theorem. Third, the detecting effect of the above method is compared with the methods of traditional BVHs, Axis-Aligned Bounding Box（AABB） tree, and Oriented Bounding Box（OBB） tree. Finally, the BVs of other organs（ear, stem, and leaf sheath） in virtual wheat plant are constructed based on their geometric morphology, and the collision detections are conducted at the organ, individual and population scales. The results indicate that the collision detection method developed in this study can accurately detect collisions between organs, especially at the plant canopy level with high collision frequency. This collision detection-based virtual crop visualization method could reduce the phenomenon of organs cross-drawing effectively and enhance the reality of visualizations.

Using LBG quantization for particle-based collision detection algorithm

Most collision detection algorithms can be efficiently used only with solid and rigid objects, for instance, Hierarchical methods which must have their bounding representation recalculated every time deformation occurs. An alternative algorithm using particle-based method is then proposed which can detect the collision among non-rigid deformable polygonal models. However, the original particle-based collision detection algorithm might not be sufficient enough in some situations due to the improper particle dispersion. Therefore, this research presents an improved algorithm which provides a particle to detect in each separated area so that particles always covered all over the object. The surface partitioning can be efficiently performed by using LBG quantization since it can classify object vertices into several groups base on a number of factors as required. A particle is then assigned to move between vertices in a group by the attractive forces received from other particles on neighbouring objects. Collision is detected when the distance between a pair of corresponding particles becomes very small. Lastly, the proposed algo- rithm has been implemented to show that collision detection can be conducted in real-time.

A collision detection approach in virtual environment of micromanipulation robot

Operators suffer much diffieulty in manipulating miero-size objects without the assistance of friendly interfaces due to the scaling effects in micro worht. The paper presented a general framework for mieromanipulation robot hased on virtual reality technology. With the framework we brought forward a FDH （Fixed Direction Hulls） based hounding box method to handle the eollision ,teteetion of the peg-in-hole mieroassembly. The eollision response model for the collision between micro needle and hole was presented. The virtual three and corresponding displacement were calculated with the model of bending deformation and pressing ,teformation. Experiments verify the validity of collision response model.

Simulating unmanned aerial vehicle flight control and collision detection

An unmanned aerial vehicle(UAV)is a small,fast aircraft with many useful features.It is widely used in military reconnaissance,aerial photography,searches,and other fields;it also has very good practical-application and development prospects.Since the UAV’s flight orientation is easily changeable,its orientation and flight path are difficult to control,leading to its high damage rate.Therefore,UAV flight-control technology has become the focus of attention.This study focuses on simulating a UAV’s flight and orientation control,and detecting collisions between a UAV and objects in a complex virtual environment.The proportional-integral-derivative control algorithm is used to control the orientation and position of the UAV in a virtual environment.A version of the bounding-box method that combines a grid with a k-dimensional tree is adopted in this paper,to improve the system performance and accelerate the collision-detection process.This provides a practical method for future studies on UAV flight position and orientation control,collision detection,etc.

A Linear Algorithm for Collision Detection of 3-Dimensional Convex Polytopes

Given two disjoint 3-dimensional convex polytopes P and Q and a straight direction along Which P moves in translation, this paper presents a linear algorithm for determining Whether P collides with Q, and the possible collision positions on P and Q. This result is achieved by using the hierarchicat representation of polytopes, of which the preprocessing time is linear with space.

COLLISION DETECTION AMONG MOVING OBJECTSIN MACHINING PROCESS SIMULATION

This paper describes an algorithm of collision detection between moving objects in machin-ing process simulation. Graphical simulation of machining has been recognized to be useful for NCprogram verification , since the programmer of the machining operator can easily find some faults inthe NC program visually. But it is difficult to visually detect collisions arnong moving objects such ascutting tools , workpieces and fixtures, a data structure to represent moving objects and an algorithmof collision detection between moving objects are proposed. A moving object can be represented by ahierarchical sphere octree and its motion can be described by a quadratic function of time. A collisionoccurs in the case that the distance between any two sphere centers in the respective two moving ob-jects is equal to the sum of the radii of these two spheres, and the radii of these two spheres are lessthan a given precision. By solving the equations that satisfy the conditions of collision between thespheres recursively , we obtain the time and the position of the collision between these two moving ob-Jects.

New collision detection method for simulating virtual plant populations

Detecting and resolving the collision of organs between different plants or the collision of different organs of a single plant are key issues in the realistic construction of a virtual plant population.A suitable collision detection scheme is necessary to prevent a reduction in realism caused by organ penetration.A mixed bounding volume tree construction scheme based on the growth characteristics of tomato plants is proposed in this paper,and the construction mode of the bounding at all levels is simplified by using a digital tomato model.Using a parallel GPU approach,we designed a tomato plant population collision detection program with CUDA acceleration.The proposed method reduces the total collision detection time by 92%-96%.

Controlling the contact levels of details for fast and precise haptic collision detection

For accurate and stable haptic rendering, collision detection for interactive haptic applications has to be done by filling in or covering target objects as tightly as possible with bounding volumes （spheres, axis-aligned bounding boxes, oriented bounding boxes, or polytopes）. In this paper, we propose a method for creating bounding spheres with respect to the contact levels of details （CLOD）, which can fit objects while maintaining the balance between high speed and precision of collision detection. Our method is composed mainly of two parts： bounding sphere formation and two-level collision detection. To specify further, bounding sphere formation can be divided into two steps： creating spheres and clustering spheres. Two-level collision detection has two stages as well： fast detection of spheres and precise detection in spheres. First, bounding spheres are created for initial fast probing to detect collisions of spheres. Once a collision is probed, a more precise detection is executed by examining the distance between a haptie pointer and each mesh inside the colliding boundaries. To achieve this refmed level of detection, a special data structure of a bounding volume needs to be defined to include all mesh information in the sphere. After performing a number of experiments to examine the usefulness and performance of our method, we have concluded that our algorithm is fast and precise enough for haptic simulations. The high speed detection is achieved through the clustering of spheres, while detection precision is realized by voxel-based direct collision detection. Our method retains its originality through the CLOD by distance-based clustering.

VGIS-COLLIDE:an effective collision detection algorithm for multiple objects in virtual geographic information system

Collision detection is an important component in simulation applications which are based on virtual geographic information system(VGIS).In this paper,an effective collision detection algorithm for multiple objects in VGIS,VGISCOLLIDE,is presented.The algorithm firstly integrates existing quadtree,which is the global hierarchical structure of VGIS,with axis-aligned bounding box of object to perform the broad-phase of collision detection.After that,exact collision detection between two objects which have passed the broad-phase of collision detection is performed.The algorithm makes no assumption about input primitives or object’s motion and is directly applicable to all triangulated models.It can be applicable to both rigid and deformable objects without preprocessing.The performance of the algorithm has been demonstrated in several environments consisting of a high number of objects with hundreds of thousands of triangles.

A Rapid Path Planner for Autonomous Ground Vehicle Using Section Collision Detection

Rapid path planner plays an important role in autonomous ground vehicle （AGV） operation. Depending on the non-holonomic kinematics constraints of AGV, its path planning problem is discussed. Since rapidly-exploring random tree （RRT） can directly take non-holonomic constraints into consideration, it is selected to solve this problem. By applying extra constraints on the movement, the generation of new configuration in RRT algorithm is simplified and accelerated. With section collision detection method applied, collision detection within the planer becomes more accurate and efficient. Then a new path planner is developed. This method complies with the non-holonomic constraints, avoids obstacles effectively and can be rapidly carried out while the vehicle is running. Simulation shows that this path planner can complete path planning in less than 0.5 s for a 170 mx 170 m area with moderate obstacle complexity.

GPU-BASED FLUID SIMULATION WITH FAST COLLISION DETECTION ON BOUNDARIES

In this paper,we present a method for fluid simulation based on smoothed particle hydrodynamic(SPH)with fast collision detection on boundaries on GPU.The major goal of our algorithm is to get a fast SPH simulation and rendering on GPU.Additionally,our algorithm has the following three features:At first,to make the SPH method GPU-friendly,we introduce a spatial hash method for neighbor search.After sorting the particles based on their grid index,neighbor search can be done quickly on GPU.Second,we propose a fast particle-boundary collision detection method.By precomputing the distance field of scene boundaries,collision detection’s computing cost arrived as O(n),which is much faster than the traditional way.Third,we propose a pipeline with fine-detail surface reconstruction,and progressive photon mapping working on GPU.We experiment our algorithm on different situations and particle numbers of scenes,and find out that our method gets good results.Our experimental data shows that we can simulate 100K particles,and up to 1000K particles scene at a rate of approximately 2 times per second.

Ultrasonic Sensor-Based Embedded System for Vehicular Collusion Detection and Alert

The efficacy of an automated collision detection system is contingent upon the caliber and volume of data at its disposal. In the event that the data is deficient, incongruous, or erroneous, it has the potential to generate erroneous positive or negative outcomes, thereby compromising the system’s credibility. The occurrence of false positives is observed when the system erroneously identifies genuine activity as collusion. The phenomenon of false negatives arises when the system is unable to identify instances of genuine collusion. Collusion detection systems are required to handle substantial volumes of data in real time, capable of analyzing relationships between different objects. The intricate nature of collusion can pose difficulties in devising and executing efficient systems for its detection. The present study proposes an automated anti-collision system that utilizes sensor devices to detect objects and activate an alert mechanism in the event that the vehicle approaches the object in close proximity. The study introduces a novel methodology for mitigating vehicular accidents by implementing a combined system that integrates collision detection and alert mechanisms. The proposed system comprises an ultrasonic sensor, a microprocessor, and an alarm system. The sensor transmits a signal to the microcontroller, which in turn sends a signal to the warning unit. The warning unit is designed to prevent potential accidents by emitting an audible warning signal through a buzzer. Additionally, the distance information is displayed on an LCD screen. The Proteus Design Suite is utilized for simulation purposes, while Arduino.cc is employed for implementation.

LSDA-APF:A Local Obstacle Avoidance Algorithm for Unmanned Surface Vehicles Based on 5G Communication Environment

In view of the complex marine environment of navigation,especially in the case of multiple static and dynamic obstacles,the traditional obstacle avoidance algorithms applied to unmanned surface vehicles(USV)are prone to fall into the trap of local optimization.Therefore,this paper proposes an improved artificial potential field(APF)algorithm,which uses 5G communication technology to communicate between the USV and the control center.The algorithm introduces the USV discrimination mechanism to avoid the USV falling into local optimization when the USV encounter different obstacles in different scenarios.Considering the various scenarios between the USV and other dynamic obstacles such as vessels in the process of performing tasks,the algorithm introduces the concept of dynamic artificial potential field.For the multiple obstacles encountered in the process of USV sailing,based on the International Regulations for Preventing Collisions at Sea(COLREGS),the USV determines whether the next step will fall into local optimization through the discriminationmechanism.The local potential field of the USV will dynamically adjust,and the reverse virtual gravitational potential field will be added to prevent it from falling into the local optimization and avoid collisions.The objective function and cost function are designed at the same time,so that the USV can smoothly switch between the global path and the local obstacle avoidance.The simulation results show that the improved APF algorithm proposed in this paper can successfully avoid various obstacles in the complex marine environment,and take navigation time and economic cost into account.

Collision-aware interactive simulation using graph neural networks

Deep simulations have gained widespread attention owing to their excellent acceleration performances.However,these methods cannot provide effective collision detection and response strategies.We propose a deep interac-tive physical simulation framework that can effectively address tool-object collisions.The framework can predict the dynamic information by considering the collision state.In particular,the graph neural network is chosen as the base model,and a collision-aware recursive regression module is introduced to update the network parameters recursively using interpenetration distances calculated from the vertex-face and edge-edge tests.Additionally,a novel self-supervised collision term is introduced to provide a more compact collision response.This study extensively evaluates the proposed method and shows that it effectively reduces interpenetration artifacts while ensuring high simulation efficiency.

CSMA/CN+: Improving the Performance of Collision Notification for Wireless LANs

In CSMA/CN, whenever inferring that a receiving frame gets corrupted, the receiver sends back its signature as a collision notification(CN) to the sender. Upon detecting an arrival of the CN, the sender will abort the ongoing transmission immediately. However, in low signal-to-interference-plus-noise ratio(SINR), the false alarm of the CN occurs frequently, which might force a sender not to transmit any frame at all. To overcome this drawback, this paper proposes CSMA/CN+ to enhance the performance of CSMA/CN. In CSMA/CN+, we introduce an additional signature. The receiver, adapting to channel conditions and self-signal suppression capability, prudently determines whether to send back zero, one, or two signatures to the sender. In this way, we can reduce or exclude false alarms and therefore improve the system performance. In this paper, we first present the design of CSMA/CN+. We then apply the design in a wireless LAN, and theoretically analyze the detection performance of the notification and the system throughput. Extensive simulations verify that CSMA/CN+ can remarkably improve the system throughput of CSMA/CN and our analysis is very accurate.

AN ALGORITHM OF DISTANCE CALCULATION BETWEEN A BOUNDING SPHERE AND A BOUNDING CSG PRIMITIVE

A simple method for calculating distance between a solid sphere and a constructive solid geometry (CSG) so lid primitive (including block, cone, cylinder, sphere, wedge and torus) is derived to support the collision detection algorithm. By decomposing the whole space into relative positions and geometric features of the sphere and the primitive considered, closed form distance formula are got. These calculations are very useful in the real time collision detection in which primitives are used as bounding volumes of complex objects.

CAD Model-Based Intelligent Inspection Planning for Coordinate Measuring Machines

As the market competition among enterprises grows intensively and the demand for high quality products increases rapidly, product quality inspection and control has become one of the most important issues of manufacturing, and improving the efficiency and accuracy of inspection is also one of problems which enterprises must solve. It is particularly important to establish rational inspection planning for parts before inspecting product quality correctly. The traditional inspection methods have been difficult to satisfy the requirements on the speed and accuracy of modern manufacturing, so CAD-based computer-aided inspection planning （CAIP） system with the coordinate measuring machines （CMM） came into being. In this paper, an algorithm for adaptive sampling and collision-free inspection path generation is proposed, aiming at the CAD model-based inspection planning for coordinate measuring machines （CMM）. Firstly, using the method of step adaptive subdivision and iteration , the sampling points for the specified number with even distribution will be generated automatically. Then, it generates the initial path by planning the inspection sequence of measurement points according to the values of each point＇s weight sum of parameters, and detects collision by constructing section lines between the probe swept-volume surfaces and the part surfaces, with axis-aligned bounding box （AABB） filtering to improve the detection efficiency. For collided path segments, it implements collision avoidance firstly aiming at the possible outer-circle features, and then at other collisions, for which the obstacle-avoiding movements are planned with the heuristic rules, and combined with a designed expanded AABB to set the obstacle-avoiding points. The computer experimental results show that the presented algorithm can plan sampling points＇ locations with strong adaptability for different complexity of general surfaces, and generate efficient optimum path in a short time and avoid collision effectively.

Computational Path Planner for Product Assembly in Complex Environments

Assembly path planning is a crucial problem in assembly related design and manufacturing processes. Sampling based motion planning algorithms are used for computational assembly path planning. However, the performance of such algorithms may degrade much in environments with complex product structure, narrow passages or other challenging scenarios. A computational path planner for automatic assembly path planning in complex 3D environments is presented. The global planning process is divided into three phases based on the environment and specific algorithms are proposed and utilized in each phase to solve the challenging issues. A novel ray test based stochastic collision detection method is proposed to evaluate the intersection between two polyhedral objects. This method avoids fake collisions in conventional methods and degrades the geometric constraint when a part has to be removed with surface contact with other parts. A refined history based rapidly-exploring random tree （RRT） algorithm which bias the growth of the tree based on its planning history is proposed and employed in the planning phase where the path is simple but the space is highly constrained. A novel adaptive RRT algorithm is developed for the path planning problem with challenging scenarios and uncertain environment. With extending values assigned on each tree node and extending schemes applied, the tree can adapts its growth to explore complex environments more efficiently. Experiments on the key algorithms are carried out and comparisons are made between the conventional path planning algorithms and the presented ones. The comparing results show that based on the proposed algorithms, the path planner can compute assembly path in challenging complex environments more efficiently and with higher success. This research provides the references to the study of computational assembly path planning under complex environments.