This paper investigates how a shepherd robot can efficiently steer a coherent group by intelligently moving behind the group in obstacle-filled environments. It was been shown that a model trained by deep reinforcement learning can guide a small number (2–4) of agents among obstacles. However, herding a larger group becomes significantly more challenging because it exhibits the characteristics similar to manipulating a deformable object, i.e., the system is dynamic and the problem is highly underactuated. To overcome these challenges, we show that a model can be trained more effectively via an optimized surrogate, such as a potential field that optimizes the control quality of the group without explicitly considering the placement of the shepherd. Our experiments demonstrate that the trained model is robust to noise for group behaviors and environments. Compared to the rule-based method, the proposed approach maintains a higher probability of guiding the sheep and better control quality.

Prototyping compact devices with unique form factors often requires the PCB manufacturing process to be outsourced, which can be expensive and time-consuming. In this paper, we present Fibercuit, a set of rapid prototyping techniques to fabricate high-resolution, flexible circuits on-demand using a fiber laser engraver. We showcase techniques that can laser cut copper-based composites to form fine-pitch conductive traces, laser fold copper substrates that can form kirigami structures, and laser solder surface-mount electrical components using off-the-shelf soldering pastes. Combined with our software pipeline, an end user can design and fabricate flexible circuits which are dual-layer and three-dimensional, thereby exhibiting a wide range of form factors. We demonstrate Fibercuit by showcasing a set of examples, including a custom dice, flex cables, custom end-stop switches, electromagnetic coils, LED earrings and a circuit in the form of kirigami crane.

Designing a robot or structure that can fold into a target shape is a process that involves challenges originated from multiple sources. For example, the designer of self-folding robots must consider foldability from geometric and kinematic aspects to avoid self-collisions and undesired deformations. Recent works have shown success in estimating foldability of a design using robot motion planners. However, many foldable structures are actuated using physically coupled reactions, e.g., folding originated from thermal, chemical, or electromagnetic loads. Therefore, a reliable folding process must consider additional constraints that result from these critical and coupled phenomena. This work investigates the idea of efficiently incorporating computationally intensive physics simulations within the folding motion planner to affect the physical folding results. We will use the manufacturing process of laser-forming origami as an example to demonstrate the benefits of considering the physical properties of the foldable structure beyond its kinematics. We show that designs produced by the proposed method can be fabricated more efficiently.

We present a novel approach for synthesizing scene-aware virtual reality teleport graphs, which facilitate navigation in indoor virtual environments by suggesting desirable teleport positions. Our approach analyzes panoramic views at candidate teleport positions by extracting scene perception graphs, which encode scene perception relationships between the observer and the surrounding objects, and predict how desirable the views at these positions are. We train a graph convolutional model to predict the scene perception scores of different teleport positions. Based on such predictions, we apply an optimization approach to sample a set of desirable teleport positions while considering other navigation properties such as coverage and connectivity to synthesize a teleport graph. Using teleport graphs, users can navigate virtual environments efficaciously. We demonstrate our approach for synthesizing teleport graphs for common indoor scenes. By conducting a user study, we validate the efficacy and desirability of navigating virtual environments via the synthesized teleport graphs. We also extend our approach to cope with different constraints, user preferences, and practical scenarios.

In this paper, we propose an optimization-based approach for automatically generating virtual scenarios for wheelchair training in virtual reality. To generate a virtual training scenario, our approach automatically generates a realistic furniture layout for a scene as well as a training path that the user needs to go through by controlling a simulated wheelchair. The training properties of the path, namely, its desired length, the extent of rotation, and narrowness, are optimized so as to deliver the desired training effects. We conducted an evaluation to validate the efficacy of the proposed virtual reality training approach. Users showed improvement in wheelchair control skills in terms of proficiency and precision after receiving the proposed virtual reality training.

Abstract Volume compaction is a geometric problem that aims to reduce the volume of a polyhedron via shape transform. Compactable structures are easier to transport and in some cases easier to manufacture, therefore, they are commonly found in our daily life (e.g. collapsible containers) and advanced technology industries (e.g., the recent launch of 60 Starlink satellites compacted in a single rocket by SpaceX). It is known in the literature that finding a universal solution to compact an arbitrary 3D shape is computationally challenging. Previous approaches showed that stripifying mesh surface can lead to optimal compaction, but the resulting structures were often impractical. In this paper, we propose an algorithm that cuts the 3D orthogonal polyhedron, tessellated by thick square panels, into a tree structure that can be transformed into compact piles by folding and stacking. We call this process tree stacking. Our research found that it is possible to decompose the problem into a pipeline of several solvable local optimizations. We also provide an efficient algorithm to check if the solution exists by avoiding the computational bottleneck of the pipeline. Our results show that tree stacking can efficiently generate stackable structures that have better folding accuracy and similar compactness comparing to the most compact stacking using strips.

The ability to edit materials of objects in images is desirable by many content creators. However, this is an extremely challenging task as it requires to disentangle intrinsic physical properties of an image. We propose an end-to-end network architecture that replicates the forward image formation process to accomplish this task. Specifically, given a single image, the network first predicts intrinsic properties, i.e. shape, illumination, and material, which are then provided to a rendering layer. This layer performs in-network image synthesis, thereby enabling the network to understand the physics behind the image formation process. The proposed rendering layer is fully differentiable, supports both diffuse and specular materials, and thus can be applicable in a variety of problem settings. We demonstrate a rich set of visually plausible material editing examples and provide an extensive comparative study.

In digital image editing software, layers organize images. However, layers are often not explicitly represented in the final image, and may never have existed for a scanned physical painting or a photograph. We propose a technique to decompose an image into layers. In our decomposition, each layer represents a single-color coat of paint applied with varying opacity. Our decomposition is based on the image’s RGB-space geometry. In RGB-space, the linear nature of the standard Porter-Duff [1984] “over” pixel compositing operation implies a geometric structure. The vertices of the convex hull of image pixels in RGB-space correspond to a palette of paint colors. These colors may be “hidden” and inaccessible to algorithms based on clustering visible colors. For our layer decomposition, users choose the palette size (degree of simplification to perform on the convex hull), as well as a layer order for the paint colors (vertices). We then solve a constrained optimization problem to find translucent, spatially coherent opacity for each layer, such that the composition of the layers reproduces the original image. We demonstrate the utility of the resulting decompositions for recoloring (global and local) and object insertion. Our layers can be interpreted as generalized barycentric coordinates; we compare to these and other recoloring approaches.

In this work, we propose a new type of visibility measurement named Continuous Visibility Feature (CVF). We say that a point q on the mesh is continuously visible from another point p if there exists a geodesic path connecting p and q that is entirely visible by p. In order to efficiently estimate the continuous visibility for all the vertices in a model, we propose two approaches that use specific CVF properties to avoid exhaustive visibility tests. CVF is then measured as the area of the continuously visible region. With this stronger visibility measure, we show that CVF better encodes the surface and part information of mesh than the tradition line-of-sight based visibility. For example, we show that existing segmentation algorithms can generate better segmentation results using CVF and its variants than using other visibility-based shape descriptors, such as shape diameter function. Similar to visibility and other mesh surface features, continuous visibility would have many applications.

The problem of image based localization has a long history both in robotics and computer vision and shares many similarities with image based retrieval problem. Existing techniques use either local features or (semi)-global image signatures in the context of topological mapping or loop closure detection. Difficulties of the location recognition problem are often affected by large appearance and viewpoint variation between the query view and reference dataset and presence of non-discriminative features due to vegetation, sky and road. In this work we show that semantic segmentation labeling of man-made structures can inform the traditional bag-of-visual words models to obtain proper feature weighting and improve the overall location recognition accuracy. We also demonstrate additional capability of identifying individual buildings and estimating their extent in images, providing the essential building block for semantic localization. Towards this end we introduce a new challenging outdoors urban dataset exhibiting large variations in appearance and viewpoint.

Self-folding robot is usually modeled as rigid origami, a class of origami whose entire surface remains rigid during folding except at crease lines. In this work, we focus on finding valid folding motion that brings the origami from the unfolded state continuously to the folded state. Although recent computational methods allow rapid simulation of folding process of certain rigid origami, these methods can fail even when the input crease pattern is extremely simple but requires implicit folding orders. Moreover, due to the rigidity requirement, the probability of generating a valid configuration via uniform sampling is zero, which greatly hinders the applicability of traditional sampling-based motion planners. We propose a novel sampling strategy that samples in the discrete domain. Our experimental results show that the proposed method could efficiently generate valid configurations. Using those configurations, the planner successfully folds several types of rigid origami that the existing methods fail to fold and could discover multiple folding paths in different homotopies.

Recent advances in robotics engineering have enabled the realization of self-folding machines. Rigid origami is usually used as the underlying model for the self-folding machines whose surface remains rigid during folding except at joints. A key issue in designing rigid origami is foldability that concerns about finding folding steps from a flat sheet of crease pattern to a desired folded state. Although recent computational methods allow rapid simulation of folding process of certain rigid origamis, these methods can fail even when the input crease pattern is extremely simple. In this paper, we take on the challenge of planning folding and unfolding motion of origami tessellations, which are composed of repetitive crease patterns. The number of crease lines of a tessellation is usually large, thus searching in such a high dimensional configuration space with the requirement of maintaining rigidity is nontrivial. We propose a motion planner that takes symmetry into consideration and reuses folding path found on the essential crease pattern. Both of these strategies enable us to fold large origami tessellation much more efficiently than existing methods. Our experimental results show that the proposed method successfully folds several types of rigid origami tessellations that existing methods fail to fold.

Maintaining clearance, or distance from obstacles and sampling efficient enough configurations on the medial axises are a vital component for successful motion planning. Maintaining high clearance often creates safer paths for robots. Having bias for sampling on medial axis also offers higher possibility to find a path in complex environment where the feasible configuration space only occupies a small proportion of the whole space. Inspired by the similarity between medial axis and max-margin scheme in optimization, especially in Support Vector Machine, we propose a new method to quickly construct the medial axis for the motion planning environment both in low and high dimensional space. However, directly applying the SVM classification on the large volume of uniformly sampled configurations suffers from huge computation and the medial axis is usually not the real medial axis due to SVM's optimization function's tolerance to the mis-classification. Instead, we show a method that can quickly push any configuration to the medial axis by using the characteristics of the Max-Margin's optimization function. Experiments in low and high dimensional space and comparisons with other medial-axis motion planning algorithm are shown.

Cut along the surface of a polyhedron and unfold it to a planar structure without overlapping is known as Unfolding Polyhedra problem which has been extensively studied in the mathematics literature for centuries. However, whether there exists a continuous unfolding motion such that the polyhedron can be continuously transformed to its unfolding has not been well studied. Recently, researchers started to recognize continuous unfolding as a key step in designing and implementation of self-folding robots. In this paper, we model the unfolding of a polyhedron as multi-link tree-structure articulated robot, and address this problem using motion planning techniques. Instead of sampling in continuous domain which traditional motion planners do, we propose to sample only in the discrete domain. Our experimental results show that sampling in discrete domain is efficient and effective for finding feasible unfolding paths.

While techniques that segment shapes into visually meaningful parts have generated impressive results, these techniques also have only focused on relatively simple shapes, such as those composed of a single object either without holes or with few simple holes. In many applications, shapes created from images can contain many overlapping objects and holes. These holes may come from sensor noise, may have important parts of the shape or may be arbitrarily complex. These complexities that appear in real-world 2D shapes can pose grand challenges to the existing part segmentation methods. In this paper, we propose a new decomposition method, called Dual-space Decomposition that handles complex 2D shapes by recognizing the importance of holes and classifying holes as either topological noise or structurally important features. Our method creates a nearly convex decomposition of a given shape by segmenting both the polygon itself and its complementary. We compare our results to segmentation produced by nonexpert human subjects. Based on two evaluation methods, we show that this new decomposition method creates statistically similar to those produced by human subjects.

Collision prediction is a fundamental operation for planning motion in dynamic environment. Existing methods usually exploit complex behavior models or use dynamic constraints in collision prediction. However, these methods all assume simple geometries, such as disc, which significantly limit their applicability. This paper proposes a new approach that advances collision prediction beyond disc robots and handles arbitrary polygons. Our new tool predicts collision by assuming that obstacles are adversarial. Comparing to an online motion planner that replans periodically at fixed time interval and planner that approximates obstacle with discs, our experimental results provide strong evidences that the new method significantly reduces the number of replans while maintaining higher success rate of finding a valid path. Our geometric-based collision prediction method provides a tool to handle highly complex shapes and provides a complimentary approach to those methods that consider behavior and dynamic constraints of objects with simple shapes.

Configuration space (C-space) plays an important role not only in motion planning but also in geometric modeling, shape and kinematic reasoning, and is fundamental to several basic geometric operations, such as continuous collision detection and generalized penetration depth estimation, that also find their applications in motion planning, animation and simulation. In this paper, we developed a new method for constructing the boundary of the C-space obstacles (C-obst) of polygons. This method is simpler to implement and is theoretically more efficient than the existing techniques. Our main idea is to devote the computation on the discontinuity in temporal and spatial coherence where the structure of the C-obst changes. We also developed a method for estimating the generalized penetration depth by computing the distance between the query point and the C-obst surface.

Computing the Minkowski sums of rotating ob jects has always been done naively by re-computing every Minkowski sum from scratch. The correspondences between the Minkowski sums are typically completely ignored. We propose a method, called DYMSUM, that can efficiently update the Minkowski sums of rotating convex polyhedra. We show that DYMSUM is significantly more efficient than the traditional approach, in particular when the size of the input polyhedra are large and when the rotation is small between frames. From our experimental results, we show that the computation time of the proposed method grows slowly with respect to the size of the input comparing to the naive approach.

We propose a new method for computing the 2-d Minkowski sum of non-convex polygons. Our method is convolution based. The main idea is to use the reduced convolution and filter the boundary by using the topological properties of the Minkowski sum. The main benefit of this proposed approach is from the fact that, in most cases, the complexity of the complete convolution is much higher than the complexity of the final Minkowski sum boundary. Therefore, the traditional approach often wastes a large portion of the computation on computing the arrangement induced by the complete convolution that is later on thrown away. Our method is designed to specifically avoid this waste of computation. We experimentally demonstrate that the proposed method is more efficient than the existing methods.

Given a motion planning problem in a dynamic but fully known environment, we propose the first roadmap-based method, called critical roadmap, that has the ability to identify and exploit the critical topological changes of the free configuration space. Comparing to the existing methods that either ignore temporal coherence or only repair their roadmaps at fixed times, our method provides not only a more complete representation of the free (configuration-time) space but also provides significant efficiency improvement. Our experimental results show that the critical roadmap method has a higher chance of finding solutions, and it is at least one order of magnitude faster than some well-known planners.

Camera control is essential in both virtual and real-world environments. The quality of the camera's placement and motion may spell the difference between usability and confusion. Our work focuses on an instance of camera control called target following, and offers an algorithm for following multiple targets with unpredictable trajectories, among known obstacles. To the best of our knowledge, this work is the first attempting to address this important problem.

Star-shaped decomposition partitions a shape into a set of star-shaped components. A shape is star shaped if and only if there exists at least one point which can see all the points in the shape. Due to this interesting property, decomposing a configuration space into star-shaped components can be beneficial, e.g., for solving motion planning problem. In this paper, we propose a simple method to decompose the contact space, represented by point set data, into approximate star-shaped components. We propose two motion planning methods, one deterministic and one probabilistic, both based on this idea.

Despite the large body of work in both motion planning and multi-agent simulation, little work has focused on the problem of planning motion for groups of robots using external ¿controller¿ agents. We call this problem the group control problem. This problem is complex because it is highly underactuated, dynamic, and requires multi-agent cooperation. In this paper, we present a variety of new motion planning algorithms based on EST, RRT, and PRM methods for shepherds to guide flocks of robots through obstacle-filled environments. We show using simulation on several environments that under certain circumstances, motion planning can find paths that are too complicated for nai¿ve ¿simulation only¿ approaches. However, inconsistent results indicate that this problem is still in need of additional study.

No abstract available.

In this paper we present a heuristic approach to planning in an environment with moving obstacles. Our approach assumes that the robot has no knowledge of the future trajectory of the moving objects. Our framework also distinguishes between two types of moving objects in the environment: hard and soft objects. We distinguish between the two types of objects in the environment as varying application domains could allow for some collision between some types of moving objects. For example, a robot planning a path in an environment with people could have the people modeled as circular disks with a safe zone surrounding each person. Although the robot may try to stay out of each safe zone, violating that criteria would not necessarily result in planning failure. We will show the effectiveness of our planner in general dynamic environments with the soft objects having varying behaviors.

Minkowski sum is a fundamental operation in many geometric applications, including robotics, penetration depth estimation, solid modeling, and virtual prototyping. However, due to its high computational complexity and several nontrivial implementation issues, computing the exact boundary of the Minkowski sum of two arbitrary polyhedra is generally a difficult task. In this work, we propose to represent the boundary of the Minkowski sum approximately using only points. Our results show that this point-based representation can be generated efficiently. An important feature of our method is its straightforward implementation and parallelization. We also demonstrate that the point-based representation of the Minkowski sum boundary can indeed provide similar functionality as mesh-based representations can. We show several applications in motion planning, penetration depth approximation and modeling.

Decomposition is a technique commonly used to partition complex models into simpler components. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we explore an alternative partitioning strategy that decomposes a given model into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition (ACD) can more accurately represent the important structural features of the model by providing a mechanism for ignoring less significant features, such as surface texture. We describe a technique for computing ACDs of three-dimensional polyhedral solids and surfaces of arbitrary genus. We provide results illustrating that our approach results in high quality decompositions with very few components and applications showing that comparable or better results can be obtained using ACD decompositions in place of exact convex decompositions (ECD) that are several orders of magnitude larger.

Comprehension of concepts and algorithms involved in the robotics field can be improved through the use of an interactive visualization tool. In this paper we present an interactive tool for visualizing and editing motion planning environments, problem instances, and their solutions. Teachers can take advantage of visualization tools to help their students to better understand motion planning and its complexity as well as the different strategies that have been developed to solve the motion planning problem. While the tool we present allows the animation, manipulation, and evaluation of solution paths found by any motion planner, it is specialized for sampling-based randomized planners such as probabilistic roadmap (PRM) and rapidly-exploring random tree (RRT) methods

Though motion planning has been studied extensively for rigid and articulated robots, motion planning for deformable objects is an area that has received far less attention. In this paper we present a framework for planning paths in completely deformable, elastic environments. We apply a deformable model to the robot and obstacles in the environment and present a kinodynamic planning algorithm suited for this type of deformable motion planning. The planning algorithm is based on the rapidly-exploring random tree (RRT) path planning algorithm. To the best of our knowledge, this is the first work that plans paths in totally deformable environments

Tree-based path planners have been shown to be well suited to solve various high dimensional motion planning problems. Here we present a variant of the Rapidly-Exploring Random Tree (RRT) path planning algorithm that is able to explore narrow passages or difficult areas more effectively. We show that both workspace obstacle information and C-space information can be used when deciding which direction to grow. The method includes many ways to grow the tree, some taking into account the obstacles in the environment. This planner works best in difficult areas when planning for free flying rigid or articulated robots. Indeed, whereas the standard RRT can face difficulties planning in a narrow passage, the tree based planner presented here works best in these areas

Shape decomposition and skeletonization share many common properties and applications. However, they are generally treated as independent computations. In this paper, we propose an iterative approach that simultaneously generates a hierarchical shape decomposition and a corresponding set of multi-resolution skeletons. In our method, a skeleton of a model is extracted from the components of its decomposition --- that is, both processes and the qualities of their results are interdependent. In particular, if the quality of the extracted skeleton does not meet some user specified criteria, then the model is decomposed into finer components and a new skeleton is extracted from these components. The process of simultaneous shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory. We provide evidence that the proposed framework is efficient and robust under perturbation and. deformation. We also demonstrate that our results can readily be used in problems including skeletal deformations and virtual reality navigation.

Shepherding behaviors are a type of group be haviors in which one group (the shepherds) tries to control the motion of another group (the flock). Shepherding behaviors can be found in many forms in nature and have various important robotic applications. In this paper we extend our previous work of shepherding behaviors with a single shepherd to multiple shepherds. More specifically, we study how a group of shepherds can work cooperatively without communication to efficiently control the flock.

We propose a strategy to decompose a polygon, containing zero or more holes, into ``approximately convex'' pieces. For many applications, the approximately convex components of this decomposition provide similar benefits as convex components, while the resulting decomposition is significantly smaller and can be computed more efficiently. Moreover, our approximate convex decomposition (ACD) provides a mechanism to focus on key structural features and ignoreless significant artifacts such as wrinkles and surface texture a user specified tolerance determines allowable concavity. We propose a simple algorithm that computes an ACD of a polygon by iteratively removing (resolving) the most significant non-convex feature (notch). As a by product, it produces an elegant hierarchical representation that provides a series of `increasingly convex' decompositions. Our algorithm computes an ACD of a simple polygon with n verticesand r notches in O(nr) time. In contrast, exact convex decomposition is NP-hard or,if the polygon has no holes, takes O(nr2) time.

No abstract available.

Shepherding behaviors are a type of flocking behavior in which outside agents guide or control members of a flock. Shepherding behaviors can be found in various forms in nature. For example, herding, covering, patrolling and collecting are common types of shepherding behaviors. In this work, we investigate ways to simulate these types of behaviors. A shepherd uses roadmaps to steer the flock and to re-group separated flock members. This paper focuses on improving the shepherd's movements to gain better control of the flock's motion and use this improved control to demonstrate a wider variety of shepherding behaviors.

We propose a general framework for sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. Generalizing our previous work, this framework provides a template encompassing all possible retraction approaches. It also removes the requirement of exactly computing distance metrics thereby enabling application to more realistic high dimensional problems. In particular, our framework supports methods that retract a given configuration exactly or approximately onto the medial axis. As in our previous work, exact methods provide fast and accurate retraction in low (2 or 3) dimensional space. We also propose new approximate methods that can be applied to high dimensional problems, such as many DOF articulated robots. Theoretical and experimental results show improved performance on problems requiring traversal of narrow passages. We also study tradeoffs between accuracy and efficiency for different levels of approximation, and how the level of approximation effects the quality of the resulting roadmap.

In this paper, we investigate methods for motion planning for deformable robots. Our framework is based on a probabilistic roadmap planner. As with traditional motion planning, the planner's goal is to find a valid path for the robot. Unlike typical motion planning, the robot is allowed to change its shape (deform) to avoid collisions as it moves along the path. We propose a two-stage approach. First, an 'approximate' path which may contain collisions is found. Next, we attempt to correct any collisions on this path by deforming the robot. We propose and analyze two methods for performing the deformations. Both techniques are inspired by a physically correct behavior, but are more efficient than completely, physically correct methods. Our approach can be applied in several domains, including flexible robots, computer modeling and animation, and biological simulations.

Flocking behavior is very common in nature, and there have been ongoing research efforts to simulate such behavior in computer animations and robotics applications. Generally, such work considers behaviors that can be determined independently by each flock member solely by observing its local environment, e.g., the speed and direction of its neighboring flock members. Since flock members are not assumed to have global information about the environment, only very simple navigation and planning techniques have been considered for such flocks. In this paper, we investigate how the addition of global information in the form of a roadmap of the environment enables more sophisticated flocking behaviors. In particular, we study and propose new techniques for three distinct group behaviors: homing, exploring and shepherding. These behaviors exploit global knowledge of the environment and utilize knowledge gathered by all flock members. This knowledge is communicated by allowing individual flock members to dynamically update the shared roadmap to reflect (un)desirable routes or regions. We present experimental results showing how the judicious use of simple roadmaps of the environment enables more complex behaviors to be obtained at minimal cost.

The explosive proliferation of networking technologies is drastically affecting operations in the health care industry. Physicians now can provide better services at lower costs through the efficient management of medical information. In recognition the importance of the interoperability of medical information, both government agencies and the private sector have made considerable investment in various medical standards, such as DICOM, HL7 and various electronic patient record systems. Among many of the standards activities, one missing element is a universal software model that would enable physicians to integrate and customize various medical information products into a complete suite for their particular needs. A software tool built on the basis of such a software model should be provably reliable, verifiable and field-configurable. It should allow instrument vendors to embed their hardware and software solutions into the tool without compromising their proprietary designs. This tool should be able to communicate and command different instruments in a consistent manner, so that new applications can be built upon well-known and well-accepted software layers. To demonstrate the effectiveness of this solution approach, we developed a portable medical information management prototype, the Portable Remote Diagnostic Information and Telemedicine System (PoRDITS).

After the introduction of VRML, 3D Web browsing has become a popular form of networked virtual reality. However, it is still a great challenge for a novice user equipped with a regular desktop PC to navigate in most virtual worlds of moderate complexity. We think the main problem is due to the fact that a user usually uses a 2D mouse to provide low-level navigation control but the display frame rate is not high enough for this servo loop. We consider an alternative metaphor of allowing a user to specify locations of interests on a 2D-layout map and let the system automatically generate the animation of guided tours in virtual architectural environments. Specifically, we aim to generate animations of customizable tour paths and its associated human/camera motions in an on-line manner according to high-level user inputs. We describe an auto-navigation system, in which several efficient path-planning algorithms adapted from robotics are used. This system has been implemented in Java and adopts common VRML browsers as its 3D interface. We also use the geometric model of our departmental building as an example to demonstrate the efficiency and effectiveness of the system.