GSST: anytime guaranteed search

We present Guaranteed Search with Spanning Trees (GSST), an anytime algorithm for multi-robot search. The problem is as follows: clear the environment of any adversarial target using the fewest number of searchers. This problem is NP-hard on arbitrary graphs but can be solved in linear-time on trees. Our algorithm generates spanning trees of a graphical representation of the environment to guide the search. At any time, spanning tree generation can be stopped yielding the best strategy so far. The resulting strategy can be modified online if additional information becomes available. Though GSST does not have performance guarantees after its first iteration, we prove that several variations will find an optimal solution given sufficient runtime. We test GSST in simulation and on a human-robot search team using a distributed implementation. GSST quickly generates clearing schedules with as few as 50% of the searchers used by competing algorithms.     

一种视点相关的大规模地形快速实时生成算法

为了解决大规模地形实时漫游过程中,由于不同细节层次模型之间过渡而引起的图像跳变以及图像绘制帧率不高的问题,提出了自底向上的一次性整体构网,网格节点实时更新的建模策略。运用基于块和三角形面片的混合裁剪模式 ,结合简化的高度差投影计算方法,快速选取适合的地形节点 ;然后采用加点、删点、局部更新三种途径对 Delaunay地形三角网进行实时更新。同时在地形漫游过程中实现了对高度差投影限的自适应控制。仿真实验表明,该算法有效地避免了图像跳变现象,与同类算法相比 ,具有较高的图像绘制帧率,特别适合大规模地形的近距离     

Parallel terrain visibility calculation on the graphics processing unit

In this paper, we present the graphics processing unit (GPU)‐based parallel implementation of visibility calculation from multiple viewpoints on raster terrain grids. Two levels of parallelism are introduced in the GPU kernels — parallel traversal of visibility rays from a single viewpoint and parallel processing of viewpoints. The obtained visibility maps are combined in parallel using the selected logical operator. A comparison with multi‐threaded CPU implementation is performed to establish the expected speed‐ups of viewshed construction when the source and destination types are sets of scattered locations, paths, or regions. The results demonstrate that using the GPU, the acceleration of an order of magnitude can be achieved on average with both point sampling and bilinear filtering of the elevation map. Copyright © 2011 John Wiley & Sons, Ltd.     

Hierarchical search support for hypertext on-line documentation

Effectively finding relevant passages in a full-text database of software documentation calls for a user interface that does more than mimic a printed book. A hypertext approach, with a network of links among passages, offers great flexibility but often at the cost of high cognitive overhead and a disorienting lack of contextual cues. A tree-based approach guides users along branching paths through a hierarchy of text nodes. The “natural”, sequential implementation of such hierarchical access, however, is psychologically inept in large databases because it is order-dependent, discriminates awkwardly among key terms, clarifies each node's context incompletely, and often involves much semantic redundancy. An alternative, mixed approach, recently implemented in the on-line documentation system at the National Energy Research Supercomputer Center (NERSC), overcomes three of these four problems. It displays only local tree structure in response to “zoomin” or “zoomout” commands issued to focus a search begun with typical hypertext moves. This combination approach enjoys the benefits of cued, spatially interpreted hierarchical search while avoiding most of its known pitfalls. Usage monitoring at NERSC shows the ready acceptance of both zoom commands by documentation readers.     

Very large-scale neighborhood search

Neighborhood search algorithms are often the most effective approaches available for solving partitioning problems, a difficult class of combinatorial optimization problems arising in many application domains including vehicle routing, telecommunications network design, parallel machine scheduling, location theory, and clustering. A critical issue in the design of a neighborhood search algorithm is the choice of the neighborhood structure, that is, the manner in which the neighborhood is defined. Currently, the two-exchange neighborhood is the most widely used neighborhood for solving partitioning problems. The paper describes the cyclic exchange neighborhood , which is a generalization of the two-exchange neighborhood in which a neighbor is obtained by performing a cyclic exchange . The cyclic exchange neighborhood has substantially more neighbors compared to the two-exchange neighborhood. This paper outlines a network optimization based methodology to search the neighborhood efficiently and presents a proof of concept by applying it to the capacitated minimum spanning tree problem, an important problem in telecommunications network design.     

一种大规模地形模型的视相关简化算法

提出了一种基于点删除的视相关简化算法。首先依据视锥准则、背离面准则和屏幕投影误差对原始网格进行可见性预处理,再对预处理后的网格依据顶点重要度大小进行点删除简化。重要度以顶点到平均平面的距离表示,在计算过程中,采用了距离加权的办法,从而进一步加强了视相关简化效果。实验表明,算法具有较高的绘制速度,并且绘制帧速率基本独立于模型的复杂度。     

Three-dimensional iterative closest point-based outdoor SLAM using terrain classification

To navigate in an unknown environment, a robot should build a model for the environment. For outdoor environments, an elevation map is used as the main world model. We considered the outdoor simultaneous localization and mapping (SLAM) method to build a global elevation map by matching local elevation maps. In this research, the iterative closest point (ICP) algorithm was used to match local elevation maps and estimate a robot pose. However, an alignment error is generated by the ICP algorithm due to false selection of corresponding points. Therefore, we propose a new method to classify environmental data into several groups, and to find the corresponding points correctly and improve the performance of the ICP algorithm. Different weights are assigned according to the classified groups because certain groups are very sensitive to the viewpoint of the robot. Three-dimensional (3-D) environmental data acquired by tilting a 2-D laser scanner are used to build local elevation maps and to classify each grid of the map. Experimental results in real environments show the increased accuracy of the proposed ICP-based matching and a reduction in matching time.     

大规模室外图像3维重建技术研究进展

基于图像的3维重建旨在从一组2维多视角图像中精确地恢复真实场景的几何形状,是计算机视觉和摄影测量中基础且活跃的研究课题,具有重要的理论研究意义和应用价值,在智慧城市、虚拟旅游、数字遗产保护、数字地图和导航等领域有着广泛应用。随着图像采集系统（智能手机、消费级数码相机和民用无人机等）的普及和互联网的高速发展,通过搜索引擎可以获取大量关于某个室外场景的互联网图像。利用这些图像进行高效鲁棒准确的3维重建,为用户提供真实感知和沉浸式体验已经成为研究热点,引发了学术界和产业界的广泛关注,涌现了多种方法。深度学习的出现为大规模室外图像的3维重建提供了新的契机。首先阐述大规模室外图像3维重建的基本串行过程,包括图像检索、图像特征点匹配、运动恢复结构和多视图立体。然后从传统方法和基于深度学习的方法两个角度,分别系统全面地回顾大规模室外图像3维重建技术在各重建子过程中的发展和应用,总结各子过程中适用于大规模室外场景的数据集和评价指标。最后介绍现有主流的开源和商业3维重建系统以及国内相关产业的发展现状。     

Multiple feature kernel hashing for large-scale visual search

Recently hashing has become attractive in large-scale visual search, owing to its theoretical guarantee and practical success. However, most of the state-of-the-art hashing methods can only employ a single feature type to learn hashing functions. Related research on image search, clustering, and other domains has proved the advantages of fusing multiple features. In this paper we propose a novel multiple feature kernel hashing framework, where hashing functions are learned to preserve certain similarities with linearly combined multiple kernels corresponding to different features. The framework is not only compatible with general types of data and diverse types of similarities indicated by different visual features, but also general for both supervised and unsupervised scenarios. We present efficient alternating optimization algorithms to learn both the hashing functions and the optimal kernel combination. Experimental results on three large-scale benchmarks CIFAR-10, NUS-WIDE and a-TRECVID show that the proposed approach can achieve superior accuracy and efficiency over state-of-the-art methods.     

A graph-based cache for large-scale similarity search engines

Large-scale similarity search engines are complex systems devised to process unstructured data like images and videos. These systems are deployed on clusters of distributed processors communicated through high-speed networks. To process a new query, a distance function is evaluated between the query and the objects stored in the database. This process relays on a metric space index distributed among the processors. In this paper, we propose a cache-based strategy devised to reduce the number of computations required to retrieve the top-k object results for user queries by using pre-computed information. Our proposal executes an approximate similarity search algorithm, which takes advantage of the links between objects stored in the cache memory. Those links form a graph of similarity among pre-computed queries. Compared to the previous methods in the literature, the proposed approach reduces the number of distance evaluations up to 60%.     

A class of intelligent agents for coordinated control of outdoor terrain mapping UGVs

This article develops a systems- and control-oriented intelligent agent framework called the hybrid intelligent control agent (HICA) and describes its composition into multiagent systems. It is essentially developed around a hybrid control system core so that knowledge-based planning and coordination can be integrated with verified hybrid control primitives to achieve the coordinated control of multiple multi-mode dynamical systems. The scheme is applied to the control of a team of unmanned ground vehicles (UGVs) engaged in an outdoor terrain mapping task. Results are demonstrated experimentally.     

Hierarchical parallel search for markov control with enhanced selector

A new method of hierarchical parallel search is proposed for dealing with Markov planning/control processes in systems with uncertain information. It is based on a new concept of analyzing alternative with uncertain cost evaluation. Under definite conditions, instead of making an immediate choice based on expectation of cost at each step of the search, it is recommended to postpone the final decision until information is improved, and the uncertainty is reduced. In addition to elementary alternatives, their combinations are also considered for possible pursuit. The best set of rough elementary solutions is to be determined at the upper of two adjacent planning/control levels, then all elementary alternatives of this set as well as their combinations, are being pursued at the lower level with a higher resolution of information, while evaluation of the remaining cost for each of the alternatives, is being constantly improved due to the process of evolutionary uncertainty reduction. This bilevel process is easily extendible over the whole hierarchy of the system. The method is working in the graph-search and dynamic programming paradigms. The set of problems to be solved is formulated and some of them are addressed. Various applications are contemplated.     

Hierarchical multi-agent planning for flexible assembly of large-scale lunar facilities

Several national space agencies and commercial aerospace companies plan to set up lunar bases with large-scale facilities that rely on multiple lunar robots’ assembly. Mission planning is necessary to achieve efficient multi-robot cooperation. This paper aims at autonomous multi-robot planning for the flexible assembly of the large-scale lunar facility, considering the harsh lunar environment, mission time optimization, and joint actions. The lunar robots and modules are scattered around the mission area without fixed assembly lines. Thus, the traditional assembly planning methods ignoring the optimal selection of modules are unable to handle this problem. We propose a hierarchical multi-agent planning method based on two-stage two-sided matching (HMAP-TTM) to solve this critical problem. First, the distributed planning framework with multi-replica public agents is introduced, ensuring robot plan knowledge consistency through public agents’ communication. Second, the hierarchical task graph (HTG) divides the mission into task layers based on task dependency knowledge. Third, we develop a novel two-stage two-sided matching algorithm. Time-optimal plans emerge from the matching games among public and private agents in each layer of HTG. Agents make decisions in the game based on action knowledge updated during planning. Finally, an assembly mission is presented to prove the method’s effectiveness. The simulation results show that the HMAP-TTM can generate plans with shorter mission time and require smaller communication costs than the baseline methods.     

Hierarchical control for large-scale systems with general multiple linear-quadratic structure

A class of large-scale linear control systems, where the overall objective function is a nonlinear function of multiple quadratic performance indices, is investigated in this paper. This type of large-scale control problem with a general multiple linear-quadratic structure is nonseparable in the sense of conventional hierarchical control. Hierarchical control is extended in this paper to large-scale nonseparable control problems, where multiobjective optimization is used as a separation strategy. The large-scale general multiple linear-quadratic control problem is embedded, under certain conditions, into a family of the weighted Lagrangian formulation. The weighted Lagrangian formulation is separable with respect to subsystems and can be effectively solved using the interaction prediction approach at the two lower levels in the proposed three-level solution structure. At the third level, the weighting vector for the weighted Lagrangian formulation is adjusted iteratively to search the optimal weighting vector with which the optimal control of the original large-scale nonseparable control problem is attained. One feature of this hierarchical control scheme is a derived analytical solution for the large-scale general multiple linear-quadratic control.     

一种用于大规模P2P点播系统的拓扑结构

提出了一种基于动态时间坐标的分层DHT拓扑结构,解决了因大规模P2P点播系统要求细粒度追踪而难以应用DHT的问题。在动态时间坐标系中,节点的播放点坐标不再随着节点的播放而移动,从而使得DHT能够用于追踪点播系统节点缓存位置。仿真结果证明了方法的有效性。     

Interactive search and browsing interface for large-scale visual repositories

Due to the rapid proliferation of both user-generated and broadcasted content, the interfaces for search and browsing of visual media have become increasingly important. This paper presents a novel intuitive interactive interface for browsing of large-scale image and video collections. It visualises underlying structure of the dataset by the size and spatial relations of displayed images. In order to achieve this, images or video key-frames are initially clustered using an unsupervised graph-based clustering algorithm. By selecting images that are hierarchically laid out on the screen, user can intuitively navigate through the collection or search for specific content. The extensive experimental results based on user evaluation of photo search, browsing and selection as well as interactive video search demonstrate good usability of the presented system and improvement when compared to the standard methods for interaction with large-scale image and video collections.     

Self-adaptive differential evolution with multi-trajectory search for large-scale optimization

In this paper, self-adaptive differential evolution (DE) is enhanced by incorporating the JADE mutation strategy and hybridized with modified multi-trajectory search (MMTS) algorithm (SaDE-MMTS) to solve large-scale continuous optimization problems. The JADE mutation strategy, the “DE/current-to-pbest” which is a variation of the classic “DE/current-to-best”, is used for generating mutant vectors. After the mutation phase, the binomial (uniform) crossover, the exponential crossover as well as no crossover option are used to generate each pair of target and trial vectors. By utilizing the self-adaptation in SaDE, both trial vector generation strategies and their associated control parameter values are gradually self-adapted by learning from their previous experiences in generating promising solutions. Consequently, suitable offspring generation strategy along with associated parameter settings will be determined adaptively to match different phases of the search process. MMTS is applied frequently to refine several diversely distributed solutions at different search stages satisfying both the global and the local search requirement. The initialization of step sizes is also defined by a self-adaption during every MMTS step. The success rates of both SaDE and the MMTS are determined and compared; consequently, future function evaluations for both search algorithms are assigned proportionally to their recent past performance. The proposed SaDE-MMTS is employed to solve the 19 numerical optimization problems in special issue of soft computing on scalability of evolutionary algorithms for large-scale continuous optimization problems and competitive results are presented.