Mobile Platform Path Planning in Structured Indoor Environment

Table of Contents

• 1. Overview

• 2. Landmark Navigation

  • Block Diagram
    

• 3. Indoor Map Representation

  • IndoorGML - Indoor Geographic Markup Language
    
  • Cellular Space Model
  • Map generation Tool
    

• 4. Path Planning

  • Mobile Platform Model
    
  • Algorithms

• 5. Simulation and Results

  • Simulation Using VREP
    
  • Analysis
  • Prototype
  • Future work
    

• References

   

1. Overview

This work shows an implementation and simulation of a path planning algorithm into an indoor structured environment.

Source Code

All the source code and project files are available through the system Bitbucket in the following link:

	https://hmontelo@bitbucket.org/hmontelo/me_396d_final_project.git

2. Landmark Navigation

Landmarks are distinct features that a mobile platform or robot can recognize from its sensory input. Landmarks can be geometric shapes (e.g., rectangles, lines, circles), and they may include additional information (e.g., in the form of bar-codes). In general, landmarks have a fixed and known position, relative to which a robot can localize itself. Landmarks are carefully chosen to be easy to identify; for example,  there must be sufficient contrast to the background. Before a robot can use landmarks for navigation, the characteristics of the landmarks must be known and stored in the robot's memory. The main task  in localization is then to recognize the landmarks reliably and to calculate the robot's position.

In order to simplify the problem of landmark acquisition it is often assumed that the current robot  position and orientation are known approximately, so that the robot only needs to look for landmarks in a limited area. For this reason good odometry accuracy is a prerequisite for successful landmark detection. The picture below shows the general procedure for performing landmark-based positioning.

Block Diagram

3. Indoor Map Representation

 A map model in the context of this report is a digital representation of an indoor environment. By creating a map model of an indoor environment, this will create a simplified manageable view of the environment. A model that will give us a better understanding of elements, description of elements, and predict how those elements will behave and interact with one another.

The application for this model will enable mobile platforms to achieve real-time indoor navigation. The complexity of an indoor environment ranges from each application, therefore to capture all the aspects of an indoor environment we need to structure the map model representation for a specific application.

IndoorGML - Indoor Geographic Markup Language

Indoor Geographical Markup Language (IndoorGML) is a standard created by the Open Geospatial Consortium (OGC) to represent and exchange geographical information, which is to build and operate indoor navigation systems. Indoor navigation comprises of route planning, localization, and tracking of subjects (i.e. people) and objects (e.g. robots or other indoor vehicles). In accordance to our application the system will incorporate a cellular space model, landmark positioning, indoor localization, and representation of mobile agents. As an established standard the focus will be using IndoorGML to create the virtual indoor environment that will achieve the desired map model representation for navigation.

Cellular Space Model

Cellular space defined as an area that is divided into cells where each particular cell has information for navigation. Cellular space has three significant properties. First, a symbolic code or a cell identifier such as a room number represents each cell. Furthermore, every cell shares a common boundary amongst other cells that never overlap. Finally, cellular space employs an (x, y, z) coordinate system to determine a precise location.

Example Indoor Environment:

In IndoorGML representation, connectivity regarding the possibility to navigate through cells is primarily derived from the semantics and topology of cells. Semantics allows for encoding characteristic information about each cell. It is used to classify cells to provide an identity for better interpretation along with using the topology to determine the connection level with other cells. An example of this would be doors, elevators, rooms, walls; all would fall into a topological layer where each cell is aware of the other cells around it to make up an entire floor plan.

It is also possible to set navigation constraints by generating options between navigable and non-navigable paths.

IndoorGML contains 5 (five) different layers:

L1 – TOPOGRAPHIC - Geometry	L2 - TOPOGRAPHIC - Navigation	L3 - SENSOR - Camera	L4 - SENSOR - Localization	L5 - TAGS - Semantic

Map Generation Tool

Design	Generated MAP (Isometric View)	Example of GML file

4. Path Planning

Mobile Platform Model (used in the simulation)

Generalized Coordinates
where:
x and y are the two coordinates of the origin P of the moving frame θ is the orientation angle of the mobile robot is the rotation angle of the right driving wheel is the rotation angle of the left driving wheel The vehicle velocity v can be found in equation in the equation: is the angular velocity of the right wheel is the angular velocity of the left wheel

Kinematic Constraints

Algorithm

A* Algorithm	Time Enhanced A* Algorithm

5. Simulation and Results

Simulation Using VREP

Analysis

• Temporal Analysis
  
  Test 1: Example of an overtaking. Two robots, 1 and 2, follow in the same direction with the same speed. Vehicle 2 overtakes the vehicle 1.

  Test2: Example of two paths without intersections.

  Test3: Example of the intersection of two Robots, followed by the passage and overtake of vehicle 2 by the vehicle 1.

  
  
  
  

• Vehicle Crossing  
  

  Using A*	Using Time Enhanced A*

   

• The implemented algorithms handles these problems in different ways. The Time enhanced A* Algorithm considers path planning and coordination simultaneously.
• The path of each vehicle is calculated according to the paths of the other vehicles. In this sense, the coordination between robots is ensured.
• The vehicles’ path is restricted to the predefined segments, while the Time enhanced A* gives the vehicle the flexibility to navigate in all free cells.
• Considering that the Time enhanced A* Algorithm includes time and movements of the other vehicles on their paths’ calculation, overtaking is allowed.
• It’s possible to conclude that the Time enhanced A* Algorithm is more flexible in the generation of paths, because the calculated paths can be adjusted according to their cost, obstacles and the other Robot movements

Prototypes

Future

References

1 U.S. Government. National Space-Based Positioning, Navigation, and Timing Coordination Office’s GPS information, 2010.

2 Open Geospatial Consortium, Inc. GML Documentation, 2010.

3 Open Geospatial Consortium, Inc. KML Documentation, 2010.

4 Open Geospatial Consortium, Inc. IndoorGML Documentation, 2014.

5 OpenStreetMap. OpenStreetMap, 2010.

6 DuToit, N. (2010). Robotic Motion Planning in Dynamic, Cluttered, Uncertain Environments. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA)

7  Knepper, R. A. and Kelly, A. (2006). High Performance State Lattice Planning Using Heuristic Look-Up Tables. In Proceedings of the IEEE-RSJ International Conference on Intelligent Robots and Systems (IROS)