Raster Voronoi Tessellation and Its Application to Emergency Modeling

Due to the advances in Web technologies,various raster maps are available through Web Map Services such as Google maps and Yahoo maps.These online maps are used to visualize diverse types of disasters.Understanding disasters with these online maps has become an important research issue.In this article,we propose a map-based general-purpose emergency management support system based on a computational model of generalized(multiplicatively weighted,order-k,and Minkowski-metric)Voronoi diagrams.The proposed system tessellates Web maps and models disasters(or emergency response units)having different weights in the complete order from 1 to k-1 in the three popular Minkowski metrics(Euclidean,Manhattan,and Maximum distance)pro-vide insightful information for various what-if emergency scenarios.The proposed map-based emergency management support system systematically supports neighboring queries,districting queries,location optimization queries,and routing queries.We pro-vide specific examples to illustrate how our system supports these queries.

Learning real-time search on c-space GVDs

In the context of robotics, configuration space （c- space） is widely used for non-circular robots to engage tasks such as path planning, collision check, and motion planning. In many real-time applications, it is important for a robot to give a quick response to the user＇s command. Therefore, a constant bound on planning time per action is severely im- posed. However, existing search algorithms used in c-space gain first move lags which vary with the size of the under- lying problem. Furthermore, applying real-time search algo- rithms on c-space maps often causes the robots being trapped within local minima. In order to solve the above mentioned problems, we extend the learning real-time search （LRTS） algorithm to search on a set of c-space generalized Voronoi diagrams （c-space GVDs）, helping the robots to incremen- tally plan a path, to efficiently avoid local minima, and to ex- ecute fast movement. In our work, an incremental algorithm is firstly proposed to build and represent the c-space maps in Boolean vectors. Then, the method of detecting grid-based GVDs from the c-space maps is further discussed. Based on the c-space GVDs, details of the LRTS and its implemen- tation considerations are studied. The resulting experiments and analysis show that, using LRTS to search on the c-space GVDs can 1） gain smaller and constant first move lags which is independent of the problem size; 2） gain maximal clear- ance from obstacles so that collision checks are much re- duced; 3） avoid local minima and thus prevent the robot from visually unrealistic scratching.