Algorithms for Nearest Neighbor Search on Moving Object Trajectories

Nearest Neighbor (NN) search has been in the core of spatial and spatiotemporal database research during the last decade. The literature on NN query processing algorithms so far deals with either stationary or moving query points over static datasets or future (predicted) locations over a set of continuously moving points. With the increasing number of Mobile Location Services (MLS), the need for effective k-NN query processing over historical trajectory data has become the vehicle for data analysis, thus improving existing or even proposing new services. In this paper, we investigate mechanisms to perform NN search on R-tree-like structures storing historical information about moving object trajectories. The proposed (depth-first and best-first) algorithms vary with respect to the type of the query object (stationary or moving point) as well as the type of the query result (historical continuous or not), thus resulting in four types of NN queries. We also propose novel metrics to support our search ordering and pruning strategies. Using the implementation of the proposed algorithms on two members of the R-tree family for trajectory data (namely, the TB-tree and the 3D-R-tree), we demonstrate their scalability and efficiency through an extensive experimental study using large synthetic and real datasets.

Multiple mini-robots navigation using a collaborative multiagent reinforcement learning framework

In this work we investigate the use of a reinforcement learning (RL) framework for the autonomous navigation of a group of mini-robots in a multi-agent collaborative environment. Each mini-robot is driven by inertial forces provided by two vibration motors that are controlled by a simple and efficient low-level speed controller. The action of the RL agent is the direction of each mini-robot, and it is based on the position of each mini-robot, the distance between them and the sign of the distance gradient between each mini-robot and the nearest one. Each mini-robot is considered a moving obstacle that must be avoided by the others. We propose suitable state space and reward function that result in an efficient collaborative RL framework. The classical and the double Q-learning algorithms are employed, where the latter is considered to learn optimal policies of mini-robots that offers more stable and reliable learning process. A simulation environment is created, using the ROS framework, that include a group of four mini-robots. The dynamic model of each mini-robot and of the vibration motors is also included. Several application scenarios are simulated and the results are presented to demonstrate the performance of the proposed approach.     

Improved Bounds for Finger Search on a RAM

We present a new finger search tree with O(loglogd) expected search time in the Random Access Machine (RAM) model of computation for a large class of input distributions. The parameter d represents the number of elements (distance) between the search element and an element pointed to by a finger, in a finger search tree that stores n elements. Our data structure improves upon a previous result by Andersson and Mattsson that exhibits expected O(loglogn) search time by incorporating the distance d into the search time complexity, and thus removing the dependence on n. We are also able to show that the search time is O(loglogd+?(n)) with high probability, where ?(n) is any slowly growing function of n. For the need of the analysis we model the updates by a “balls and bins” combinatorial game that is interesting in its own right as it involves insertions and deletions of balls according to an unknown distribution.     

Modeling of multiple mobile manipulators handling a common deformable object

The dynamic equations of motion for a system of multiple mobile manipulators carrying a common deformable object are developed. The derived centralized model is based on Kane's approach to dynamics. The imposed kinematic nonholonomic constraints are included and incorporated into the dynamics. It is pointed out, however, that these kinematic constraints are only necessary, and they only become sufficient to impose nonholonomic motion when accompanied by the dynamic counterparts. Sufficient conditions for avoiding tipping over by the mechanisms are also provided. The whole set of constraint equations is analyzed and useful properties for the set of admissible solutions for the ground reaction forces are obtained. The deformable object under manipulation is modeled and the simplest approximating grid structure is indicated. © 1998 John Wiley & Sons, Inc.     

A biomimetic approach to inverse kinematics for a redundant robot arm

Redundant robots have received increased attention during the last decades, since they provide solutions to problems investigated for years in the robotic community, e.g. task-space tracking, obstacle avoidance etc. However, robot redundancy may arise problems of kinematic control, since robot joint motion is not uniquely determined. In this paper, a biomimetic approach is proposed for solving the problem of redundancy resolution. First, the kinematics of the human upper limb while performing random arm motion are investigated and modeled. The dependencies among the human joint angles are described using a Bayesian network. Then, an objective function, built using this model, is used in a closed-loop inverse kinematic algorithm for a redundant robot arm. Using this algorithm, the robot arm end-effector can be positioned in the three dimensional (3D) space using human-like joint configurations. Through real experiments using an anthropomorphic robot arm, it is proved that the proposed algorithm is computationally fast, while it results to human-like configurations compared to previously proposed inverse kinematics algorithms. The latter makes the proposed algorithm a strong candidate for applications where anthropomorphism is required, e.g. in humanoids or generally in cases where robotic arms interact with humans.     

Effective problem solving through fuzzy logic knowledge bases aggregation

Cooperative problem solving has attracted great interest in the research community. A number of nodes can cooperate to reach a common goal which is the solution to a specific problem. Through a team effort, nodes try to achieve the best possible result. Each node undertakes the responsibility to fulfill a specific task (part of a complex plan towards the solution of the problem) and return the final outcome to a coordinator. The coordinator assigns tasks to nodes and, accordingly, collects the results. In this paper, we propose the adoption of fuzzy logic (FL) in the decision making process of each node. Nodes adopt the provided (by the coordinator) FL knowledge base that indicates the appropriate actions during the problem solving process. This knowledge base is updated during the execution of the assigned task to be fully aligned with the environment characteristics. Partial knowledge bases experienced by the nodes are sent back to the coordinator and are aggregated to generate a ‘global’ knowledge base that incorporates the experience retrieved by the team. We describe the aggregation process and propose two models: the first adopts the immediate distribution of the aggregated FL rule base to the active nodes and the second indicates the future use of the aggregated FL rule base. Our evaluation involves the realization of the proposed framework in a specific research domain as well as numerical results retrieved by a large number of simulations. Our results show that there is a trade-off between the two proposed models concerning the quality of the final solution and the time required to retrieve the final outcome.     

Efficient algorithm for transferring a real-time HEVC stream with haptic data through the internet

It is widely accepted that the growth of Internet and the improvement of Internet’s network conditions helped real-time applications to flourish. The demand for Ultra-High Definition video is constantly increasing. Apart from video and sound, a new kind of real-time data is making its appearance, haptic data. The efficient synchronization of video, audio, and haptic data is a rather challenging effort. The new High-Efficiency Video Coding (HEVC) is quite promising for real-time ultra-high definition video transferring through the Internet. This paper presents related work on High-Efficiency Video Coding. It points out the challenges and the synchronization techniques that have been proposed for synchronizing video and haptic data. Comparative tests between H.264 and HEVC are undertaken. Measurements for the network conditions of the Internet are carried out. The equations for the transferring delay of all the inter-prediction configurations of the HEVC are defined. Finally, it proposes a new efficient algorithm for transferring a real-time HEVC stream with haptic data through the Internet.