SPACE

FIELD OF INVENTION

[001] The present invention relates broadly, but not exclusively, to systems and methods for mapping a navigational space.

BACKGROUND

[002] Geofencing involves the use of Global Positioning System (GPS) satellite network and/or local radio-frequency identifiers (such as Wi-Fi nodes or Bluetooth beacons) to create virtual boundaries around a location. The geofence may be then paired with a hardware/software application that responds to the virtual boundary in some pre-defined manner.

[003] For example, geofencing can be used to control the movements of unmanned aerial vehicles (i.e. "drones") to prevent access to restricted areas such as airports, military sites, sport stadiums, etc. The drone needs a reliable navigation system (e.g. GPS) and autopilot software to interact with a geofence. For example, a five kilometer "no-fly-zone" can be set around an airport. The drone's autopilot may store the position (latitude and longitude) of the airport. As the drone flies, the autopilot continually computes the distance between itself and the airport. When the drone reaches five kilometers within the airport, the autopilot responds with a maneuver and/or notifies the pilot to do something.

[004] However, there are a few drawbacks associated with the current geofencing technique described above. For example, an airspace is only modelled as a single 3D volume based on an area covered and an altitude of the airspace covered. Moreover, the current geofencing technique is not able to indicate whether an unmanned aerial vehicles is near a boundary of a geofenced area (restricted airspace). Furthermore, the current geofencing technique can only cater to a simple volumetric geofence within a larger geofence area. [005] A need therefore exists to provide systems and methods for mapping a navigational space that seek to address at least some of the above problems.

SUMMARY

[006] According to a first aspect, there is provided a method for mapping a navigational space, comprising: defining a base layer of three-dimensional (3D) polygons that is distributed over a base of the navigational space, wherein a height of each 3D polygon of the base layer is the same; and defining one or more upper layers of 3D polygons that are above the base layer of 3D polygons, wherein each 3D polygon of the base layer and the one or more upper layers demarcates a distinct volume of the navigational space.

[007] According to a second aspect, there is provided a system for mapping a navigational space, comprising: a processor module; a memory module including computer program code; the memory module and the computer program code configured to, with the processor module, cause the system at least to: define a base layer of three-dimensional (3D) polygons that is distributed over a base of the navigational space, wherein a height of each 3D polygon of the base layer is the same; and define one or more upper layers of 3D polygons that are above the base layer of 3D polygons, wherein each 3D polygon of the base layer and the one or more upper layers demarcates a distinct volume of the navigational space.

BRIEF DESCRIPTION OF THE DRAWINGS

[008] Embodiments and implementations are provided by way of example only, and will be better understood and readily apparent to one of ordinary skill in the art from the following written description, read in conjunction with the drawings, in which:

[009] Figure 1 shows a formation of 2D polygons on a map, according to an example embodiment;

[0010] Figures 2a and 2b show size adjustability of 2D polygons, according to an example embodiment; [0011] Figures 3a and 3b show a formation of 3D polygons, according to an example embodiment;

[0012] Figure 4 shows a cross-section of a base of a navigational space, according to an example embodiment;

[0013] Figure 5 shows a formation of 3D polygons on a map, according to an example embodiment;

[0014] Figure 6 shows a cross-section of a navigational space, according to an example embodiment;

[0015] Figure 7 shows a cross-section of a navigational space defined with no-fly zones, according to an example embodiment;

[0016] Figure 8 shows a formation of 3D polygons on a map, each of the 3D polygons assigned an aircraft accessibility attribute, according to an example embodiment;

[0017] Figure 9 shows a flow chart illustrating a method for mapping a navigational space, according to an example embodiment; and

[0018] Figure 10 shows a schematic diagram of a computer system suitable for use in executing at least some steps of the method for mapping a navigational space and/or for realizing at least a part of the system for for mapping a navigational space.

DETAILED DESCRIPTION

[0019] Embodiments will be described, by way of example only, with reference to the drawings. Like reference numerals and characters in the drawings refer to like elements or equivalents.

[0020] Some portions of the description which follows are explicitly or implicitly presented in terms of algorithms and functional or symbolic representations of operations on data within a computer memory. These algorithmic descriptions and functional or symbolic representations are the means used by those skilled in the data processing arts to convey most effectively the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities, such as electrical, magnetic or optical signals capable of being stored, transferred, combined, compared, and otherwise manipulated.

[0021] Unless specifically stated otherwise, and as apparent from the following, it will be appreciated that throughout the present specification, discussions utilizing terms such as "receiving", "scanning", "calculating", "determining", "replacing", "generating", "initializing", "outputting", or the like, refer to the action and processes of a computer system, or similar electronic device, that manipulates and transforms data represented as physical quantities within the computer system into other data similarly represented as physical quantities within the computer system or other information storage, transmission or display devices.

[0022] The present specification also discloses apparatus for performing the operations of the methods. Such apparatus may be specially constructed for the required purposes, or may comprise a computer or other device selectively activated or reconfigured by a computer program stored in the computer. The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various machines may be used with programs in accordance with the teachings herein. Alternatively, the construction of more specialized apparatus to perform the required method steps may be appropriate. The structure of a computer suitable for executing the various methods / processes described herein will appear from the description below.

[0023] In addition, the present specification also implicitly discloses a computer program, in that it would be apparent to the person skilled in the art that the individual steps of the method described herein may be put into effect by computer code. The computer program is not intended to be limited to any particular programming language and implementation thereof. It will be appreciated that a variety of programming languages and coding thereof may be used to implement the teachings of the disclosure contained herein. Moreover, the computer program is not intended to be limited to any particular control flow. There are many other variants of the computer program, which can use different control flows without departing from the spirit or scope of the invention.

[0024] Furthermore, one or more of the steps of the computer program may be performed in parallel rather than sequentially. Such a computer program may be stored on any computer readable medium. The computer readable medium may include storage devices such as magnetic or optical disks, memory chips, or other storage devices suitable for interfacing with a computer. The computer readable medium may also include a hard-wired medium such as exemplified in the Internet system, or wireless medium such as exemplified in the GSM mobile telephone system. The computer program when loaded and executed on such a computer effectively results in an apparatus that implements the steps of the preferred method.

[0025] Embodiments of the invention relate to systems and methods for mapping a navigational space, such as an airspace. The navigational space is layered and segregated into a plurality of three-dimensional (3D) polygons. Each 3D polygon can be used to demarcate a distinct volume of the navigational space. Each 3D polygon can be easily identified and managed. The layering of different altitudes in the navigational space advantageously allows each layer in the navigational space to be used for different applications or different type of flying entities.

[0026] Figure 1 shows a formation of two-dimensional (2D) polygons on a map, according to an example embodiment. An array of 2D polygons (e.g. polygons 102a, 102b, 102c, ...) are formed on the map 104. In Figure 1 , the 2D polygons (e.g. 1 02a, 1 02b, 1 02c, ...) are squares. However, the 2D polygons can be defined to be any shape (e.g. rectangle, hexagon, triangle, etc.), and the shape can be chosen based on the characteristics of the navigational space.

[0027] In Figure 1 , the 2D polygons (e.g. 1 02a, 102b, 102c, ...) are adjoined to their immediate neighbouring polygon. For example, polygon 102a is adjoined to both polygon 102b to the right and polygon 102c to the bottom. In this manner, the array of 2D polygons is formed over the entire map without any discontinuity or gaps. In an alternative implementation, the array of 2D polygons is not formed over certain portions of the map.

[0028] By forming the array of 2D polygons (e.g. 102a, 1 02b, 1 02c, ...) on the map 104, a navigational space delimited by the map 104 is segregated into a plurality of 2D polygons. Each 2D polygon (e.g. 102a, 102b, 102c, ...) demarcates a distinct area of the navigational space. As a result, a visual 2D representation of the horizontal planar map 104 is obtained.

[0029] Figures 2a and 2b show size adjustability of 2D polygons, according to an example embodiment. In particular, the size or area of each 2D polygon can be adjusted to cater to different geographic terrain topology requirements or to cater to different user requirements (e.g. smaller polygon areas for more precise segregation of the navigational space). With reference to Figure 2a, the original area of the square 202 can be increased 204 or decreased 206. Likewise, with reference to Figure 2b, the original area of the hexagon 21 2 can be increased 214 or decreased 21 6.

[0030] Figures 3a and 3b show a formation of 3D polygons, according to an example embodiment. Each of the 2D polygons described above can be elevated upwards by certain height to form a 3D volumetric polygon. Each polygon preferably has an adjustable minimum vertical clearance height (H), which defines a 3D polygon volume. With reference to Figure 3a, the square 202 can be elevated upwards by height (H) to form 3D volumetric polygon 302. Likewise, with reference to Figure 3b, the hexagon 212 can be elevated upwards by height (H) to form 3D volumetric polygon 312.

[0031] Figure 4 shows a cross-section of a base of a navigational space 400, according to an example embodiment. A base layer 402 of three-dimensional (3D) polygons (e.g. 402a, 402b, 402c, ...) is defined. The base layer 402 is distributed over a base 404 of the navigational space 400. A height (H) of each 3D polygon (e.g. 402a, 402b, 402c, ...) of the base layer 402 is the same. Preferably, the height (H) of each 3D polygon (e.g. 402a, 402b, 402c, ...) of the base layer is defined with reference to a mean sea level (MSL) of the navigational space.

[0032] Figure 5 shows a formation of 3D polygons on a map, according to an example embodiment. In particular, figure 5 shows a partial formation of a base layer of 3D polygons (e.g. polygons 502a, 502b, 502c, 502d) on a map that is similar to the horizontal planar map 104. Each 3D polygon of the base layer (e.g. 502a, 502b, 502c, 502d) demarcates a distinct volume of the navigational space.

[0033] Figure 6 shows a cross-section of a navigational space, according to an example embodiment. One or more upper layers of 3D polygons can be defined above the base layer of 3D polygons. Similarly, each 3D polygon of the one or more upper layers demarcates a distinct volume of the navigational space.

[0034] For example, to form the one or more upper layers of 3D polygons, the base layer of 3D polygons can be duplicated to form adjacent upper layers of 3D polygons. The polygon height in the upper layers can be varied depending on the usage of the particular layer of polygons at the airspace. It will be appreciated that any number of stacks / layers of 3D polygons can defined.

[0035] As shown in figure 6, the navigational space 600 is represented or mapped by seven stacks / layers of 3D polygons. The height of each layer (H1 to HN) is adjustable. H1 is set with reference to MSL so as to maintain uniformity across all terrain.

[0036] Figure 7 shows a cross-section of a navigational space defined with no-fly zones, according to an example embodiment. Figure 7 is similar to figure 6, except that some of the 3D polygons in figure 7 have been defined as no-fly zones. For example, 3D polygons 702 are defined as airspace accessible volumes, 3D polygons 704 are defined as airspace accessible volumes that are near boundaries of airspace inaccessible volumes, and 3D polygons 706 are defined as airspace inaccessible volumes (i.e. no-fly zones).

[0037] Figure 8 shows a formation of 3D polygons on a map, each of the 3D polygons assigned an aircraft accessibility attribute, according to an example embodiment.

[0038] Each 3D polygon shown in figure 8 is assigned an aircraft accessibility attribute, such as being designated as an "airspace in-accessible" volume 806 or an "airspace accessible" volume 802. "Airspace in-accessible" volume units 806 can be defined as a no-fly zone in the 3D airspace. "Airspace accessible" volume units 802 can be defined as a fly zone in the 3D airspace. Volume units 804 can be defined as "boundary" volume units which are airspace accessible volumes that are near boundaries of airspace inaccessible volumes.

[0039] "Airspace in-accessible" volume units can be defined as a no-fly zones due to the possibilities of the following: 1 ) Airports; 2) Selected zone at a selected timeframe whereby flying of UAV is forbidden, e.g. Festivals, Parades, Sports events; 3) Sensitive or Military zone; and 4) Building structures. For example, if a particular volume of the navigational space encompasses a skyscraper, the corresponding 3D polygon can be defined as an "airspace in-accessible" volume 806.

[0040] Figure 9 shows a flow chart 900 illustrating a method for mapping a navigational space, according to an example embodiment. Step 902 involves defining a base layer of three-dimensional (3D) polygons that is distributed over a base of the navigational space. A height of each 3D polygon of the base layer is the same. Preferably, the height of each 3D polygon of the base layer is defined with reference to a mean sea level (MSL) of the navigational space.

[0041] Subsequently, step 904 involves defining one or more upper layers of 3D polygons that are above the base layer of 3D polygons. Each 3D polygon of the base layer and the one or more upper layers demarcates a distinct volume of the navigational space.

[0042] The step 902 that is directed to defining the base layer may comprise defining a (base) area, or a width and length, of each 3D polygon of the base layer. Likewise, the step 904 that is directed to defining the one or more upper layers may comprise defining an area, or a width and length, of each 3D polygon of the one or more upper layers.

[0043] The area or width / length of each 3D polygon of the one or more upper layers may be defined to be the same as the area or width / length of a corresponding 3D polygon of the base layer.

[0044] Optionally, the area or width / length of each 3D polygon of the base layer and the one or more upper layers can be defined based on a geographic topology of the navigational space. For example, the geographical topology of a mountain can be modelled as a "NO-FLY" zone with blocks of non-accessible 3D polygons from the base to the upper layers.

[0045] The step 904 that is directed to defining the one or more upper layers may comprise defining a height of each 3D polygon of the one or more upper layers.

[0046] In an implementation, the height of each 3D polygon of the base layer and the one or more upper layers may be defined to be equal to or more than a pre-determined height (i.e. a minimum height). The height of each 3D polygon of the base layer and the one or more upper layers can be defined to be the same or different, depending on specific requirements or applications.

[0047] Preferably, all the 3D polygons of the base layer are adjoining such that a continuous base layer is formed over the base of the navigational space. Similarly, all the 3D polygons of each upper layer are adjoining such that a continuous layer is formed over its immediate neighbouring lower layer. [0048] The method may further comprise a step 906 of assigning an aircraft accessibility attribute to each 3D polygon of the base layer and the one or more upper layers. The aircraft accessibility attribute specifies whether the distinct volume of the navigational space demarcated by each 3D polygon is accessible or inaccessible to aircrafts. The aircraft accessibility attribute can be dynamically assigned as and when needed. For example, a central database server can contain a database comprising aircraft accessibility attributes. The database can be accessed and referenced at all times to facilitate dynamic airspace management.

[0049] The method may further comprise: receiving at least one input value; selecting an appropriate height for at least one of the 3D polygons from a library based on the at least one input value; and defining the height of the at least one of the 3D polygons to correspond to the selected appropriate height.

[0050] In an implementation, there is provided a system for mapping a navigational space. The system comprises a processor module and a memory module including computer program code. The memory module and the computer program code are configured to, with the processor module, cause the system at least to: (i) define a base layer of three-dimensional (3D) polygons that is distributed over a base of the navigational space; and (ii) define one or more upper layers of 3D polygons that are above the base layer of 3D polygons. Each 3D polygon of the base layer and the one or more upper layers demarcates a distinct volume of the navigational space.

[0051] A height of each 3D polygon of the base layer is the same. Further, the height of each 3D polygon of the base layer may be defined with reference to a mean sea level (MSL) of the navigational space.

[0052] The system may be further caused to define a (base) area, or width and length, of each 3D polygon of the base layer and the one or more upper layers. The area, or width and length, of each 3D polygon of the one or more upper layers can be defined to be the same as the area, or width and length, of a corresponding 3D polygon of the base layer. The area, or width and length, of each 3D polygon of the base layer and the one or more upper layers can be defined based on a geographic topology of the navigational space. The area, or width and length, of each 3D polygon of the base layer and the one or more upper layers can be defined to be the same or to be different. [0053] The system can be further caused to define a height of each 3D polygon of the one or more upper layers. The height of each 3D polygon of the base layer and the one or more upper layers may be defined to be equal to or more than a pre-determined height. Optionally, the height of each 3D polygon of the base layer and the one or more upper layers are not defined to be the same. In an example implementation, the system can comprise a database storage module / non-volatile memory module having stored therein a library containing a plurality of pre-defined heights for a 3D polygon. The system can be configured to receive at least one input value, including but not limited to: a flying object's properties, a location of the navigational space, rules governing the use of the navigational space and rules governing the flight of the flying object. Based on the input values received, the system can be further caused to select an appropriate height (H) from the library, e.g. based on an algorithm. The selected height is defined to be the height of one or more 3D polygons. In other words, the system can be configured to automatically determine an appropriate height (H) for at least one 3D polygon based on one or more input variables. For example, if the flying object is an unmanned aerial vehicle (drone), the appropriate height (H) that is selected may be less than if the flying object is a passenger aircraft. Due to the size of a drone being much smaller than a passenger aircraft, the system can define a height of each 3D polygon of the one or more upper layers to be less so as to provide more accurate geofencing.

[0054] Accordingly, in an exemplary embodiment, a library of heights is stored in the memory module, and the system is further caused to: receive at least one input value; select an appropriate height for at least one of the 3D polygons from the library based on the at least one input value; and define the height of the at least one of the 3D polygons to correspond to the selected appropriate height.

[0055] Preferably, all the 3D polygons of the base layer are adjoining such that a continuous base layer is formed over the base of the navigational space.

[0056] In an implementation, the system is further caused to assign an aircraft accessibility attribute to each 3D polygon of the base layer and the one or more upper layers. The aircraft accessibility attribute specifies whether the distinct volume of the navigational space demarcated by each 3D polygon is accessible or inaccessible to aircrafts. The aircraft accessibility attribute can be dynamically assigned based on a date and time. The system can be connected to a central database server, and the central database server contains a database comprising aircraft accessibility attributes. The database can be accessed and referenced at all times to facilitate dynamic airspace management.

[0057] By segregating and layering the airspace into a plurality of 3D polygon blocks, the airspace can be easily identified and managed. Moreover, as mentioned above, each 3D polygon can be categorised into a fly zone or no-fly zone, which in turns allows dynamic management of airspace which is required in Unmanned Traffic Management System (UTMS) for Unmanned Aerial Vehicles (UAVs). Moreover, embodiments allow a layering of different altitudes in the airspace, where each layer can cater for different applications or different type of flying entities.

[0058] The above-described multi-layer 3D polygon map is particularly useful in the application of UAVs. In particular, the location of UAVs can be easily identified and managed. Furthermore, the adoption of multi-layer 3D polygon mapping can facilitate airspace division management such that the airspace can be utilized by different aviation entities. The airspace management includes layering of altitudes meant for different airspace domain applications and classification of NO-FLY zones or FLY zones. In this manner, an active geofence mechanism can be efficiently deployed as it can enable pre-emptive actions to be initiated once the UAV is near to a boundary of a NO-FLY zone since an anticipated handover polygon is known based on the direction the UAV is heading.

[0059] Figure 10 shows a schematic diagram of a computer system suitable for use in executing at least some steps of the method for mapping a navigational space and/or for realizing at least a part of the system for for mapping a navigational space.

[0060] Figure 10 shows a schematic diagram of a computer system / system 1000 suitable for use in executing at least some steps of the method for mapping a navigational space and/or for realizing at least a part of the system for for mapping a navigational space. The following description of the computing device 1000 is provided by way of example only and is not intended to be limiting.

[0061] As shown in Figure 10, the example computing device 1000 includes a processor 1004 for executing software routines. Although a single processor is shown for the sake of clarity, the computing device 1000 may also include a multi-processor system. The processor 1004 is connected to a communication infrastructure 1006 for communication with other components of the computing device 1000. The communication infrastructure 1006 may include, for example, a communications bus, cross-bar, or network.

[0062] The computing device 1000 further includes a main memory 1008, such as a random access memory (RAM), and a secondary memory 1010. The secondary memory 1010 may include, for example, a hard disk drive 1012 and/or a removable storage drive 1014, which may include a magnetic tape drive, an optical disk drive, or the like. The removable storage drive 1014 reads from and/or writes to a removable storage unit 1018 in a well-known manner. The removable storage unit 1018 may include a magnetic tape, optical disk, or the like, which is read by and written to by removable storage drive 1014. As will be appreciated by persons skilled in the relevant art(s), the removable storage unit 1018 includes a computer readable storage medium having stored therein computer executable program code instructions and/or data.

[0063] In an alternative implementation, the secondary memory 1010 may additionally or alternatively include other similar means for allowing computer programs or other instructions to be loaded into the computing device 1000. Such means can include, for example, a removable storage unit 1022 and an interface 1020. Examples of a removable storage unit 1022 and interface 1020 include a removable memory chip (such as an EPROM or PROM) and associated socket, and other removable storage units 1022 and interfaces 1020 which allow software and data to be transferred from the removable storage unit 1022 to the computer system 1000.

[0064] The computing device 1000 also includes at least one communication interface 1024. The communication interface 1024 allows software and data to be transferred between computing device 1000 and external devices via a communication path 1026. In various embodiments, the communication interface 1024 permits data to be transferred between the computing device 1000 and a data communication network, such as a public data or private data communication network. The communication interface 1024 may be used to exchange data between different computing devices 1000 which such computing devices 1000 form part an interconnected computer network. Examples of a communication interface 1024 can include a modem, a network interface (such as an Ethernet card), a communication port, an antenna with associated circuitry and the like. The communication interface 1024 may be wired or may be wireless. Software and data transferred via the communication interface 1024 are in the form of signals which can be electronic, electromagnetic, optical or other signals capable of being received by communication interface 1024. These signals are provided to the communication interface via the communication path 1026.

[0065] Optionally, the computing device 1000 further includes a display interface 1002 which performs operations for rendering images to an associated display 1030 and an audio interface 1032 for performing operations for playing audio content via associated speaker(s) 1034.

[0066] As used herein, the term "computer program product" may refer, in part, to removable storage unit 1018, removable storage unit 1022, a hard disk installed in hard disk drive 1012, or a carrier wave carrying software over communication path 1026 (wireless link or cable) to communication interface 1024. Computer readable storage media refers to any non-transitory tangible storage medium that provides recorded instructions and/or data to the computing device 1000 for execution and/or processing. Examples of such storage media include floppy disks, magnetic tape, CD-ROM, DVD, Blu-ray™ Disc, a hard disk drive, a ROM or integrated circuit, USB memory, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computing device 1000. Examples of transitory or non-tangible computer readable transmission media that may also participate in the provision of software, application programs, instructions and/or data to the computing device 1000 include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like.

[0067] The computer programs (also called computer program code) are stored in main memory 1008 and/or secondary memory 1010. Computer programs can also be received via the communication interface 1024. Such computer programs, when executed, enable the computing device 1000 to perform one or more features of embodiments discussed herein. In various embodiments, the computer programs, when executed, enable the processor 1004 to perform features of the above-described embodiments. Accordingly, such computer programs represent controllers of the computer system 1000.

[0068] Software may be stored in a computer program product and loaded into the computing device 1000 using the removable storage drive 1014, the hard disk drive 1012, or the interface 1020. Alternatively, the computer program product may be downloaded to the computer system 1000 over the communications path 1026. The software, when executed by the processor 1004, causes the computing device 1000 to perform functions of embodiments described herein.

[0069] It is to be understood that the embodiment of Figure 10 is presented merely by way of example. Therefore, in some embodiments one or more features of the computing device 1000 may be omitted. Also, in some embodiments, one or more features of the computing device 1000 may be combined together. Additionally, in some embodiments, one or more features of the computing device 1000 may be split into one or more component parts.

[0070] It will be appreciated by a person skilled in the art that numerous variations and/or modifications may be made to the present invention as shown in the specific embodiments without departing from the spirit or scope of the invention as broadly described. The present embodiments are, therefore, to be considered in all respects to be illustrative and not restrictive.