[go: up one dir, main page]

WO2008129488A2 - Système et procédé pour le recalcul de probabilités dans des arbres de décision - Google Patents

Système et procédé pour le recalcul de probabilités dans des arbres de décision Download PDF

Info

Publication number
WO2008129488A2
WO2008129488A2 PCT/IB2008/051495 IB2008051495W WO2008129488A2 WO 2008129488 A2 WO2008129488 A2 WO 2008129488A2 IB 2008051495 W IB2008051495 W IB 2008051495W WO 2008129488 A2 WO2008129488 A2 WO 2008129488A2
Authority
WO
WIPO (PCT)
Prior art keywords
probability
devices
location
hypothesis
circle
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/IB2008/051495
Other languages
English (en)
Other versions
WO2008129488A3 (fr
Inventor
Paul R. Simons
Stephen M. Pitchers
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Koninklijke Philips NV
Original Assignee
Koninklijke Philips Electronics NV
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Koninklijke Philips Electronics NV filed Critical Koninklijke Philips Electronics NV
Publication of WO2008129488A2 publication Critical patent/WO2008129488A2/fr
Publication of WO2008129488A3 publication Critical patent/WO2008129488A3/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H05—ELECTRIC TECHNIQUES NOT OTHERWISE PROVIDED FOR
    • H05B—ELECTRIC HEATING; ELECTRIC LIGHT SOURCES NOT OTHERWISE PROVIDED FOR; CIRCUIT ARRANGEMENTS FOR ELECTRIC LIGHT SOURCES, IN GENERAL
    • H05B47/00—Circuit arrangements for operating light sources in general, i.e. where the type of light source is not relevant
    • H05B47/10—Controlling the light source
    • H05B47/175—Controlling the light source by remote control
    • H05B47/19—Controlling the light source by remote control via wireless transmission
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01S—RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
    • G01S5/00—Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations
    • G01S5/02—Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations using radio waves
    • G01S5/0205—Details
    • G01S5/0244—Accuracy or reliability of position solution or of measurements contributing thereto
    • H—ELECTRICITY
    • H05—ELECTRIC TECHNIQUES NOT OTHERWISE PROVIDED FOR
    • H05B—ELECTRIC HEATING; ELECTRIC LIGHT SOURCES NOT OTHERWISE PROVIDED FOR; CIRCUIT ARRANGEMENTS FOR ELECTRIC LIGHT SOURCES, IN GENERAL
    • H05B47/00—Circuit arrangements for operating light sources in general, i.e. where the type of light source is not relevant
    • H05B47/10—Controlling the light source
    • H05B47/175—Controlling the light source by remote control
    • H05B47/198—Grouping of control procedures or address assignation to light sources
    • H05B47/199—Commissioning of light sources
    • H—ELECTRICITY
    • H05—ELECTRIC TECHNIQUES NOT OTHERWISE PROVIDED FOR
    • H05B—ELECTRIC HEATING; ELECTRIC LIGHT SOURCES NOT OTHERWISE PROVIDED FOR; CIRCUIT ARRANGEMENTS FOR ELECTRIC LIGHT SOURCES, IN GENERAL
    • H05B47/00—Circuit arrangements for operating light sources in general, i.e. where the type of light source is not relevant
    • H05B47/10—Controlling the light source
    • H05B47/175—Controlling the light source by remote control
    • H05B47/198—Grouping of control procedures or address assignation to light sources
    • H05B47/199—Commissioning of light sources
    • H05B47/1995—Auto-commissioning
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W64/00—Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Definitions

  • the present systems and methods relate to recalculation of probabilities in decision trees where nodes are automatically assigned to their correct spatial positions within a network, such as a wirelessly controlled lighting array.
  • a typical wireless lighting array comprises a large number of electrically driven luminaires, which are typically positioned to provide a uniform light distribution, for example.
  • the luminaires within the array are often positioned in a grid or lattice arrangement in the ceiling of a room such that there is uniform spacing between them.
  • Each of the individual luminaires in such a lighting array is adapted such that it is able to communicate with the other luminaires over a wireless communication network, which is formed by an array of associated communication nodes.
  • Each of the communication nodes in the network is located at the position of its associated luminaire in the lighting array.
  • the communication network provides a means by which the lighting array can be auto-commissioned post-installation.
  • the individual nodes in the network are unable to provide their own position information, therefore, it is not known which luminaire is associated with which node.
  • the spatial position of each node in the communication network is established via a variety of known methods, including via manual operator input, for example, so that each node can be assigned to the correct luminaire.
  • the positions of the communication nodes are found by a trilateration process, for example, which is based upon range data provided by the wireless communication network.
  • the range data is provided in the form of range measurements taken between pairs of communication nodes in the wireless network.
  • the calculation of a range between two nodes is derived directly from these range measurements, which are made using known techniques such as using Received Signal Strength Indication (RSSI) or Time-of-Flight information of signal exchanged between various nodes and/or luminaires.
  • RSSI Received Signal Strength Indication
  • the received strength of a radio signal exchanged between a pair of communication nodes is used to calculate the range between them.
  • the strength of the transmitted signal decreases at a rate inversely proportional to the distance traveled and proportional to the wavelength of the signal.
  • the distance between the pair of nodes may be calculated from the transmitted signal's attenuation at the receiving node.
  • the range between a pair of communication nodes is calculated by measuring the time taken for a radio signal to travel between them. Since radio signals travel at the speed of light, an accurate measure of the time-of-flight between the pair of nodes enables an accurate calculation of the distance between them.
  • the communication nodes In order for the wireless lighting array to be successfully commissioned, the communication nodes must be assigned to their correct grid or lattice position, and hence luminaire, in the lighting array. If the communication nodes are assigned to a lattice position which does not correspond to their actual lattice position, the derived spatial structure of the communication network will be incorrect and, and consequently, the lighting array will not function correctly.
  • the positions derived by trilateration may be compared with a template which defines the lattice positions of the luminaires in the lighting array.
  • a communication node may be assigned to the closest luminaire to its derived position. Its new position may then be used as a reference point in the trilateration of further communication nodes. In this way, errors in the positions derived by the trilateration process are not accumulated.
  • Position determination may be achieved using various algorithms, such as one described in an article entitled "An Algorithm for Tracking Multiple Targets” by Donald B. Reid, IEEE Transactions on Automatic Control, volume AC-24, No. 6, pages 843-854, December 1979, used to track moving objects, which is incorporated herein by reference in its entirety.
  • Reid's algorithm has been widely applied to defense systems, particularly for the target-tracking domain. As described in Reid, trees of hypotheses are constructed to represent the possible options for assigning incoming data to existing tracks. Keeping these options open allows the final decision to be delayed until more information is available.
  • One object of the present systems and methods is to improve known systems and methods of commissioning target devices, such as luminaires, in a network.
  • method and system are provided for determining probabilities in a decision tree comprising generating a first hypothesis having a first probability of a first device being at a first location based on distances from the first device to two devices; generating a second hypothesis having a second probability for a second device being at a second location based on distances from the second device to the first device and to the two devices; and recalculating the first probability to form a recalculated first probability based on distances from the first device to the second device and to the two known devices.
  • Fig. 1 shows a plan showing network node positions and the target devices according to one illustrative embodiment
  • Fig. 2 shows a block diagram of section of the wireless lighting network shown in Fig. 1 ;
  • Fig. 3 shows a system for automatic commissioning of devices according to an illustrative embodiment
  • Fig. 4 shows a processing device according to an illustrative embodiment
  • Figs. 5-10 show examples illustrating recalculation of probabilities according to illustrative embodiments.
  • the present systems and methods use hypothesis trees to represent and resolve the assignment decisions made during the automatic commissioning of target devices in a network, such as luminaires used in a lighting network or system.
  • Decisions trees are used to evaluate problems in which multiple outcomes are possible in order to help determine the most plausible solution.
  • the tree includes a hierarchy of hypotheses, each of which assigns a certain probability to a particular belief. The branch with the highest overall probability represents the best guess at the correct solution.
  • the present systems and methods include techniques to improve the estimation of probability for each hypothesis, which is a crucial in auto-commissioning of target devices, such as luminaires, in a network including a lighting system, for example.
  • present systems and methods provide improved trilateration, as more data becomes available, leading to better probability calculation, and may be used to reduce the possibility of the correct hypothesis from being eliminated. Further, the present systems and methods correct early stages of decision tree building when information availability is often limited. Thus, significant improvement in results of the completed decision tree is achieved. Further, the present systems and methods are less sensitive to the order in which beliefs are created.
  • Decision trees are used to represent alternative hypotheses to solve a particular problem.
  • Each hypothesis is assigned a probability indicating the likelihood that a certain belief is correct, such as that a certain device is located at a specified location marked on the building plan, for example.
  • the hypotheses are organized into a tree structure such that the combination of hypotheses along a particular branch of the tree indicates a combined view of a set of assignments of target devices (such as luminaires) to locations.
  • the likelihood of a particular belief is derived from range data measured from the positions of devices positioned by earlier hypotheses in the tree.
  • Each branch of the tree represents one possible set of assignments of devices to locations. From two known devices used as reference points provided manually via user input or determined via known methods for example, trilateration is used to determine the relative position of an unknown-position third/new or target device from measured distances between the third/new or new target device and each reference point.
  • Each trilateration operation uses the history of the assignments on its own branch as the starting arrangement to which the new device placement should be added.
  • Each branch constitutes a unique starting arrangement for the trilateration operation.
  • Earlier assignments on that branch are treated as known reference positions for creating a new belief.
  • the range from the device to each of the reference points is used to estimate the position of the new device.
  • the distance between that position and the various locations specified in the building plan is taken into account in determining the likelihood of the new device being at each location specified in the building plan or map.
  • the probability of the parent of each hypothesis is also taken into account when determining the overall probability of each new hypothesis.
  • the present systems and methods provide for feeding information back in the reverse direction to improve the estimated probability of earlier hypotheses.
  • Decision trees are used to resolve the positions of wireless devices, for example, using range measurements made between the devices.
  • the range measurements may incorporate large range errors, and the decision tree helps to deal with the resulting uncertainty.
  • the decision tree provides a mechanism of examining all plausible allocations of devices to the locations in the building plan.
  • Fig. 1 shows a building plan or map including a wireless network 100, for example, with six nodes at known locations A, B, C, D, E and F and six wireless devices, e.g., using the ZigBeeTM protocol or other wireless protocols, such as six luminaires 1, 2, 3, 4, 5 and 6.
  • a scan of the wireless network reveals the identities of the wireless devices 1, 2, 3, 4, 5 and 6.
  • the task or auto-commissioning involves determining which identity or target device (e.g., luminaire) 1, 2, 3, 4, 5 and 6 is associated with which location A, B, C, D, E and F of the network, e.g., in a building or any other environment.
  • target device e.g., luminaire
  • the present systems and methods are applicable for auto-commissioning of any network and any target devices.
  • the nodes 210 and/or luminaires are adapted to communicate with one another through the wireless communication network 100, which comprises wireless communication nodes 220, such as the six nodes at locations A, B, C, D, E and F shown in Fig. 1.
  • Each of the communication nodes 220 comprises, for example, a ZigBee-like radio module, and is associated with one of the electrically driven luminaires 210.
  • the hardware present at each luminaire's position comprises a power supply unit 230, a wireless communication node 220 and a luminaire 210.
  • the power supply unit 230 is adapted to provide electrical power to the communication node(s) 220 and/or to the luminaire(s) 210.
  • the power supply unit(s) 230 may be connected to a mains power supply (e.g., 120V AC, 60Hz or 230V, 50Hz for example) and may comprise electrical components such as transformers for manipulating the mains supply and providing power to the nodes 220 and luminaires 210.
  • the first stage in commissioning the lighting array of the luminaires 210 is to establish the communication network.
  • Every communication node 220 in the network 100 tunes to a control channel and broadcasts an "advertise" message, which contains its node type and a request that all other nodes identify themselves. After a certain time, each other node replies to the message with its identity and functionality. However, the nodes 220 and/or luminaires 210 are typically unable to supply their position information. At this stage, therefore, the spatial structure of the network 100 is unknown. Fig.
  • the system 300 comprises placement algorithm 310 stored in a memory for execution by a processor or CPU 410 shown in Fig. 4.
  • the positions of the nodes 220 in the network 100 may be established with the use of the placement algorithm 310.
  • the placement algorithm 310 is configured to calculate the relative position of each node 220 using range data provided by the wireless communication network 100.
  • the range data is provided in the form of range measurements taken between pairs of communication nodes 220 in the wireless network 100.
  • the calculation of a range between a pair of the six nodes A to F is derived directly from these range measurements, which may be made using techniques like Received Signal Strength Indication (RSSI) or Time-of-Flight information, for example.
  • RSSI Received Signal Strength Indication
  • Time-of-Flight information for example.
  • the placement algorithm 310 is adapted such that it may be implemented, for example, by a processing device 400 (shown in Fig. 4) such as a laptop computer or PDA which communicates with nodes 220 of the wireless network 100 through a gateway interface 320.
  • the processing device 400 may include the gateway interface 320, and memory for storing the placement algorithm 310, as well as other algorithm and data such as an operating system and the like.
  • the gateway interface 320 comprises a computer or processor executable program, running on the processor 410 of processing device 400 shown in Fig. 4, which requests and collects data from the communication network 100 through a gateway provided by one of the communication nodes 220.
  • the collected data includes the functionality of each node 220 and range measurements between each pair of nodes 220.
  • the gateway interface 320 continuously monitors the network 100 and is configured to detect if new nodes are added to, or disappear from, the network 100.
  • the hardware of the processing device 400 includes a processor such as central processing unit (CPU) 410 for executing the placement algorithm 310 and for managing and controlling the operation of the computer 400.
  • the CPU 410 is connected to a number of devices via a bus 420, the devices including a storage device, for example a hard disk drive 430, and memory devices including ROM 440 and RAM 450 for storing application algorithm and data for execution and processing by the CPU 410.
  • the computer hardware further includes a network card 450, which provides means for interfacing to the communication network 100, and a display 460, which allows a user to monitor the operation of the computer 400.
  • any other input/output device may also be provided, such as a keyboard, mouse etc.
  • the computer 400 is configured to communicate with the gateway via a serial or Ethernet cable, for example. However, the computer 400 may communicate with the gateway wirelessly.
  • the placement algorithm 310 is adapted such that it may be implemented by computer hardware which is integrated into the wireless communication network 100.
  • Such hardware may be, for example, part of the communication nodes 220 and/or the luminaires 210, for example.
  • the processor 410 of the computer 400 requests and receives range data from the wireless communication network 100 through the gateway provided by one of the communication nodes 220.
  • the computer 400 uses the range data to implement the placement algorithm 310.
  • Figs. 5-10 illustrate the method by which the placement algorithm 310 uses range measurements to derive the positions of the four luminaires 1, 2, 3, 5 in the network 100, starting with known positions of luminaires 4 and 6, provided manually by a system operator or user, for example, or determined via any other means.
  • luminaires 4 and 6 are already known to be in locations A and B, respectively, which may be determined by known methods, including via manual input from the system user, for example, as well as using the methods described in International Patent Application Serial Number PCT/IB2007/050707, for example.
  • the processor 410 when executing the placement algorithm 310 may then use range measurements from these reference positions A and B to determine the most likely identities of the devices 1, 2, 3 and 5, in the remaining positions C, D, E and F.
  • transceivers and detectors of the nodes 220 and/or luminaires 210 communicate with other and exchange signals, from which distances may be determined, such as using RSSI or Time-of-Flight information.
  • Fig. 5 shows the first level of a decision tree 500 and hypothesis Hl and H2, having probabilities as indicated by reference numerals 510, 520, respectively, showing circles 530, 540 having radii representing distance or range data as measured, e.g., via RSSI or Time-of-Flight methods.
  • One circle 530 is generated, e.g., from measured range data between location-unknown device 1 and location-known or first reference device 4.
  • the circle 530 has a center at the node located at position A, where the location-known luminaire 4 is also located, and a radius which is equal to the measured distance between the luminaire 4 (or node A) and the location-unknown luminaire 1 , whose position or location within the network or building plan, map or lighting array, is being determined.
  • Luminaire 1 is selected from among other luminaires of unknown or yet to be determined positions, since it is the closest luminaire to the two reference luminaires or target devices 4, 6 of known locations (namely, located at locations A and B, respectively). This closeness of the luminaire 1 to at least one of the two reference luminaires 4, 6 may also be determined using RSSI or Time-of-Flight methods, for example.
  • the next closest luminaire to at least one of the three position-known luminaires 1, 4, 6 is selected for determination of the position of this next closest luminaire.
  • the other circle 540 (generated from distance or range measurement between location-unknown device 1 and location-known or reference device 6) has a center at the node located at position B, where the reference luminaire 6 is also located, and a radius which is equal to the measured distance between the reference luminaire 6 (or node B) and the closest luminaire 1 whose position is to be determined.
  • Initial range or distance measurements are performed between the first position-known device 4 and position-unknown devices and/or range measurements between the second position-known device 6 and the position-unknown devices. From such closeness measurements, the closest position-unknown device to at least one of the two position-known devices 4, 6 is selected for its position determination, namely, luminaire 1 in the illustrative example shown in Fig. 5.
  • the initial range measurements indicate that target device or luminaire 1 is the closest to known reference points 4 and 6 so it is selected to be placed next. Further range measurements are made between the position-unknown device 1 and the first position-known device 4, and between the position-unknown device 1 and the second position-known device 6.
  • the two range circles 530, 540 produce an intersection point 550 of the two range circles 530, 540, as shown in Fig. 5.
  • This intersection point 550 is compared with the four locations C, D, E, and F that have not yet been assigned a target device. For the sake of clarity only the closest two target or possible locations D and E for location-unknown device 1 are illustrated. Further, the tree is routinely pruned to prevent the unnecessary expansion of hypotheses with a very low probability.
  • Hypothesis Hl represents the assignment of device 1 to location D
  • hypothesis H2 represents the assignment of device 1 to location E.
  • each hypothesis Hl, H2 is calculated based on the distance from the intersection point 550 to the target locations D or E.
  • the decision tree 500 has two outcomes, possibilities or branches 560, 570 representing hypothesis Hl (having probability 510) and hypothesis H2 (having probability 520). Since the intersection point 550 is closer to location D than to location E, then the first branch 560, representing hypothesis Hl (having probability 510), is allocated a higher likelihood or probability, namely, 0.75, which is higher than the probability of 0.25 for hypothesis H2 (having probability 520) associated with the second branch 570 of the decision tree 500.
  • Fig. 6 shows the next level of the decision tree 600, which considers the assignment of device 2.
  • hypotheses H3, H4, H5, H6 (having calculated probabilities 610, 620, 630, 640, respectively,) are created, namely, two child hypotheses H3, H4 created from the first branch 560 from parent hypothesis Hl (having probability 510) and two child hypotheses H5, H6 created from the second branch 570 starting from parent hypothesis H2 (having probability 520).
  • Three reference points are now available, namely the three position-known devices 1, 4, 6, thus enabling three range circles 650, 655, 660 to be drawn to produce an intersection point 665, for hypotheses H3, H4.
  • the first circle 650 represents the range area from device 2/location E to device 4/location A; the second circle 655 represents the range area from device 2/location E to device 6/location B; and the third circle 660 represents the range area from device 2/location E to device I/location D.
  • the first circle 650 has a center at device 4/location A and a radius being the measured distance between device 2 (and/or node at location E) and device 4 (and/or node at location A), e.g., via RSSI and/or Time-of-Flight measured data from signals exchanged between device 2/location E and device 4/location A;
  • the second circle 655 has a center at device 6/location B and a radius being the measured distance between device 2/location E and device 6/location B;
  • the third circle 660 has a center at device I/location D and a radius being the measured distance between device 2/location E and device I/location D.
  • the three circles intersect at various locations.
  • An average intersection point or position 665 is determined by averaging the positions derived from the best set of intersections, as described in International Patent Application Serial Number PCT/IB2006/054921, filed on December 18, 2006, claiming the benefit of European Patent Application Serial Number 05112465.9, to Pitchers et ah, entitled "A Method and Apparatus for Determining the Location of Nodes in a Wireless Network” filed on December 20, 2005, (Attorney Docket No. PH003798, IDs 405346, 406150), which are both incorporated herein by reference in their entirety.
  • the fourth circle 670 has a center at device 4/location A and a radius being the measured distance between device 4/location A and device 2/location F;
  • the fifth circle 675 has a center at device 6/location B and a radius being the measured distance between device 6/location B and device 2/location F;
  • the sixth circle 680 has a center at device I/location E and a radius being the measured distance between device I/location E and device 2/location F.
  • the likelihood or probability 610, 620, 630, 640 of each of the four child hypotheses H3, H4, H5, H6 is proportional to or based on the distances from the intersection point 665, 685 to the target locations. Additionally, an overall or combined probability is assigned by multiplying this likelihood of the particular branch or child by the probability of the parent hypothesis. As shown in Fig.
  • Hypothesis H3 (having probability 610) has the highest overall probability of 0.50 as it inherits a good probability (of 0.75) from hypothesis Hl (having probability 510), and yields a close intersection point 665 to target location E (hypothesis H3), which is closer than the distance from the intersection point 665 to the target location F of hypothesis H4, where it is hypothesized or assumed that the device 2 is at location F. Accordingly, luminaire 1 is assigned to location D and luminaire 2 is assigned to location E since hypothesis H3 has the highest probability 610 as compared to the other probabilities 620, 630, 640 at the same tree level, i.e., the second level of the decision tree 600.
  • hypothesis H3 may be chosen if its probability exceeds a predetermined value, which may depend on the number of branches at the particular tree level.
  • the predetermined level may be 1/4, so the branch(es) or hypothesis having a probability of greater than 1/4 or 0.25 is selected as providing the correct assignment of luminaires to nodes or locations.
  • the present systems and methods include an additional step that improves the calculation of probabilities, by re-evaluating previous levels of hypotheses. As each created child hypotheses represents an assignment of a device to a position, the re-evaluation may also use the child hypotheses to provide additional reference positions.
  • Fig. 7 revisits the calculation of probabilities of hypotheses Hl and H2, after hypotheses H3, H4, H5 and H6 have been created where their overall probabilities 610, 620, 630, 640 are 0.50, 0.24, 0.05 and 0.21, as shown in Fig. 6. As shown in Fig.7, and by comparison to Fig.
  • recalculating the probability 610' for hypothesis H3' includes generating a new circle 710 having a center at device 2 located at position E and a radius which is equal to the measured distance between the device 2 (and/or node E) and the device 1 (and/or node D).
  • the intersections of this circle 710 with previously generated circles 530, 540 (as described in connection with Fig. 5), as well as other intersections of the three circles 530, 540, 710 are evaluated.
  • Intersections that have a low probability, i.e., are far away from possible nodes or locations (e.g., location D) of device 1 are pruned or discarded, and an average intersection point 750 is determined from the remaining intersections near the possible location D, for example, to provide improved trilateration.
  • the distance from the intersection point 750 of the three generated circles 530, 540, 710 to device 1 (position D) is less than the distance from the intersection point 550 to device 1 (position D) shown in Fig. 5.
  • the recalculated probability 510' of device 1 being at position D is greater than the probability 510 of 0.75 for hypothesis Hl, resulting in a larger overall probability 610' for hypothesis H3' of 0.57 (as shown in Fig. 7) which is greater than previously calculated overall probability 610 of 0.50 for hypothesis H3, as shown in Fig. 6. Accordingly, it is more likely that the correct position of device 1 is location D and the correct position of device 2 is location E. That is, once the recalculated probabilities are factored in to the overall probability for each branch, it should be noted that the overall trilateration result for hypothesis H3' has improved, increasing its overall likelihood 610' to 0.57 as shown in Fig.
  • probabilities 620', 630', 640' are recalculated to yield 0.24, 0.02 and 0.21 for the other three hypotheses H4', H5', H6', respectively, via similar trilateration, using the additional circles 720, 730 ,740 in combination with circles 530, 540.
  • hypothesis H5' inherits a worse trilateration result from hypothesis H2' reducing its probability 630' to just 0.02 as shown in Fig.7 (from the probability 630 of 0.05 shown in Fig 6.).
  • the recalculation indicates that hypothesis H3' is the most internally consistent set of assignments, namely, device 1 at location D, device 2 at location E, while devices 4 and 6 are at locations A and B, respectively.
  • the worst trilateration 755 is for hypothesis H2', where it is assumed that device 2 is located at position D and device 1 is located at position E.
  • This re-evaluation technique may be applied as each new level of created hypotheses, constantly feeding back information to improve the parent hypotheses for every hypothesis in the tree. In fact, it is the probabilities of these leaf or child hypotheses H3, H4, H5 and H6 that are most significant. It is not in actually necessary to modify the probabilities of intermediate hypotheses, provided the overall total probability is independently recalculated along each branch of the decision tree. By postponing the re-evaluation until the tree has been fully completed, the amount of processing time can be greatly reduced.
  • this example causes only subtle changes to the probabilities, but this technique can be applied when many levels of hypotheses have been built.
  • subtle changes in probability when calculated over a number of levels may cause more dramatic changes, as the revised probabilities are fed back up the hypothesis structure from parent to child until they reach the top level.
  • Figs. 8-10 show another example of triangulation to determine device location in a network, i.e., to assign devices 1 to 10 (shown in Fig. 10) to nodes or locations A to J, shown in the array 800 Fig. 8.
  • Fig. 9 shows a typical triangulation result 900 as the decision tree is constructed.
  • Device 5 is considered as a plausible assignment for location E, but as the assignments for locations F to J have yet to be established. Consequently, the triangulation result shown by averaged intersection points 910, 920 has a poor geometry, as indicated by two possible positions 910, 920 for Device 5, where one average intersection point or position 910 is close to location E, while the other average intersection point 920 is close to location F.
  • a typical triangulation without re- evaluation leads to a rather low triangulation result, even though one of the assignments, namely, assignment of device 5 to locations E is in fact the correct one.
  • Fig. 9 shows a typical triangulation result 900 as the decision tree is constructed.
  • Device 5 is considered as a plausible assignment for location E, but as the assignments for locations F to J have yet to be established. Consequently, the triangulation result shown by averaged intersection points 910, 920 has a poor geometry, as indicated by two possible positions 910,
  • mapping 1000 which takes into account re-evaluating the intersection points once the remaining positions have been placed by child hypotheses.
  • the use of the new information has expanded the set of reference positions for trilateration, improving the geometry and therefore improving the reliability of the probability calculation.
  • both possible outcomes or intersection points 1010, 1020 for Device 5 are at the correct location, namely, location E.
  • re-evaluation provides accurate estimates of probability reduce the chances of the correct solution being pruned.
  • Re-evaluation at the completion of the tree provides the most accurate probabilities when determining the most plausible solution.
  • the present systems and methods for re-evaluating outcomes by feeding information back in reverse to improve the estimated probability of earlier hypotheses may be applied wherever decisions need to be made in the face of uncertainty.
  • the re- evaluation technique may significantly improve the estimation of probability for each alternative solution.
  • the various components of the re-evaluation system such as the various nodes, target devices, processor 410, memories 440, 450, hard disk 430, various circuit cards such as the network card 450 and display 460 shown in Fig. 4, for example, may be interconnected through any type of bus, for example, or operationally coupled to each other by any type of link, including wired or wireless link(s), for example.
  • the processor 410, memories 440, 450, and hard disk 430 may be centralized or distributed among the various system components where, for example, each target device may have its own controller or processor and memory.
  • various elements may be included in the system or network components for communication, such as transmitters, receivers, or transceivers, antennas, modulators, demodulators, converters, duplexers, filters, multiplexers etc.
  • the communication or links among the various system components may be by any means, such as wired or wireless for example.
  • the system elements may be separate or integrated together, such as with the processor.
  • the processor executes instructions stored in the memory, for example, which may also store other data, such as predetermined or programmable settings related to system control.
  • Various modifications may also be provided as recognized by those skilled in the art in view of the description herein.
  • the operation acts of the present methods are particularly suited to be carried out by a computer software program.
  • the computer software program may contain modules corresponding to the individual steps or acts of the methods.
  • the application data and other data are received by the controller or processor for configuring it to perform operation acts in accordance with the present systems and methods.
  • Such software, application data as well as other data may of course be embodied in a computer-readable medium, such as an integrated chip, a peripheral device or memory, such as the memory or other memory coupled to the processor of the controller or light module.
  • the computer-readable medium and/or memory may be any recordable medium (e.g., RAM, ROM, removable memory, CD-ROM, hard drives, DVD, floppy disks or memory cards) or may be a transmission medium (e.g., a network comprising fiber-optics, the world- wide web, cables, and/or a wireless channel using, for example, time-division multiple access, code-division multiple access, or other wireless communication systems). Any medium known or developed that can store information suitable for use with a computer system may be used as the computer-readable medium and/or memory.
  • a recordable medium e.g., RAM, ROM, removable memory, CD-ROM, hard drives, DVD, floppy disks or memory cards
  • a transmission medium e.g., a network comprising fiber-optics, the world- wide web, cables, and/or a wireless channel using, for example, time-division multiple access, code-division multiple access, or other wireless communication systems.
  • the computer-readable medium, the memory, and/or any other memories may be long-term, short-term, or a combination of long- and-short term memories. These memories configure the processor/controller to implement the methods, operational acts, and functions disclosed herein.
  • the memories may be distributed or local and the processor, where additional processors may be provided, may be distributed or singular.
  • the memories may be implemented as electrical, magnetic or optical memory, or any combination of these or other types of storage devices.
  • the term "memory" should be construed broadly enough to encompass any information able to be read from or written to an address in the addressable space accessed by a processor. With this definition, information on a network, such as the Internet, is still within or part of the memory, for instance, because the processor may retrieve the information from the network.
  • the processors and the memories may be any type of processor/controller and memory.
  • the processor may be capable of performing the various described operations and executing instructions stored in the memory.
  • the processor may be an application- specific or general-use integrated circuit(s).
  • the processor may be a dedicated processor for performing in accordance with the present system or may be a general-purpose processor wherein only one of many functions operates for performing in accordance with the present system.
  • the processor may operate utilizing a program portion, multiple program segments, or may be a hardware device utilizing a dedicated or multi-purpose integrated circuit.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Position Fixing By Use Of Radio Waves (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

L'invention concerne un système et un procédé pour déterminer des probabilités dans un arbre de décision (700), qui comprennent un processeur configuré pour générer une première hypothèse (H1) ayant une première probabilité (510) d'un premier dispositif (1) qui est à un premier emplacement (D) sur la base de distances du premier dispositif (1) à deux dispositifs (4, 6); générer une seconde hypothèse (H3) ayant une seconde probabilité (610) pour un second dispositif (2) qui est à un second emplacement (E) sur la base de distances du second dispositif (2) au premier dispositif (1) et aux dispositifs (4, 6); et recalculer la première probabilité (510) pour former une première probabilité recalculée (510') sur la base de distances du premier dispositif (1) au second dispositif (2) et aux deux dispositifs connus (4, 6).
PCT/IB2008/051495 2007-04-24 2008-04-18 Système et procédé pour le recalcul de probabilités dans des arbres de décision Ceased WO2008129488A2 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
EP07106848.0 2007-04-24
EP07106848 2007-04-24

Publications (2)

Publication Number Publication Date
WO2008129488A2 true WO2008129488A2 (fr) 2008-10-30
WO2008129488A3 WO2008129488A3 (fr) 2008-12-18

Family

ID=39776980

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/IB2008/051495 Ceased WO2008129488A2 (fr) 2007-04-24 2008-04-18 Système et procédé pour le recalcul de probabilités dans des arbres de décision

Country Status (2)

Country Link
TW (1) TW200850056A (fr)
WO (1) WO2008129488A2 (fr)

Cited By (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2010064167A3 (fr) * 2008-12-04 2010-12-02 Koninklijke Philips Electronics N.V. Procédés de sélection et dispositifs de commande
WO2011055259A1 (fr) * 2009-11-03 2011-05-12 Koninklijke Philips Electronics N.V. Réseau d'éclairage avec détection d'objet et système de commande associé
ITVI20100235A1 (it) * 2010-08-13 2012-02-14 St Microelectronics Srl Sistema di localizzazione per il monitoraggio dell'illuminazione stradale
EP2685793A1 (fr) * 2012-07-12 2014-01-15 LG Innotek Co., Ltd. Système et procédé de commande d'éclairage
WO2014011497A1 (fr) * 2012-07-09 2014-01-16 Ilumisys, Inc. Système et procédé de commande du fonctionnement d'une lumière à del
US8840282B2 (en) 2010-03-26 2014-09-23 Ilumisys, Inc. LED bulb with internal heat dissipating structures
US8901823B2 (en) 2008-10-24 2014-12-02 Ilumisys, Inc. Light and light sensor
US9013119B2 (en) 2010-03-26 2015-04-21 Ilumisys, Inc. LED light with thermoelectric generator
US9285084B2 (en) 2013-03-14 2016-03-15 Ilumisys, Inc. Diffusers for LED-based lights
US9510400B2 (en) 2014-05-13 2016-11-29 Ilumisys, Inc. User input systems for an LED-based light
US9574717B2 (en) 2014-01-22 2017-02-21 Ilumisys, Inc. LED-based light with addressed LEDs
US9585216B2 (en) 2008-10-24 2017-02-28 Ilumisys, Inc. Integration of LED lighting with building controls
US9839102B2 (en) 2012-07-12 2017-12-05 Lg Innotek Co., Ltd. Lighting control method and lighting control system
US10036549B2 (en) 2008-10-24 2018-07-31 Ilumisys, Inc. Lighting including integral communication apparatus
US10161568B2 (en) 2015-06-01 2018-12-25 Ilumisys, Inc. LED-based light with canted outer walls
EP3672335A1 (fr) * 2018-12-21 2020-06-24 Signify Holding B.V. Procédé et dispositif pour la mise en service d'un système d'éclairage

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8118447B2 (en) 2007-12-20 2012-02-21 Altair Engineering, Inc. LED lighting apparatus with swivel connection
US8324817B2 (en) 2008-10-24 2012-12-04 Ilumisys, Inc. Light and light sensor
US9267650B2 (en) 2013-10-09 2016-02-23 Ilumisys, Inc. Lens for an LED-based light

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7714778B2 (en) * 1997-08-20 2010-05-11 Tracbeam Llc Wireless location gateway and applications therefor
US6807537B1 (en) * 1997-12-04 2004-10-19 Microsoft Corporation Mixtures of Bayesian networks
US20040198386A1 (en) * 2002-01-16 2004-10-07 Dupray Dennis J. Applications for a wireless location gateway
FI113410B (fi) * 2002-05-31 2004-04-15 Ekahau Oy Probabilistinen malli paikannustekniikkaa varten
US7181393B2 (en) * 2002-11-29 2007-02-20 Microsoft Corporation Method of real-time speaker change point detection, speaker tracking and speaker model construction
US7424300B2 (en) * 2003-05-23 2008-09-09 Symbol Technologies, Inc. Method for tracking location of a mobile unit

Cited By (39)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8901823B2 (en) 2008-10-24 2014-12-02 Ilumisys, Inc. Light and light sensor
US10182480B2 (en) 2008-10-24 2019-01-15 Ilumisys, Inc. Light and light sensor
US11333308B2 (en) 2008-10-24 2022-05-17 Ilumisys, Inc. Light and light sensor
US10973094B2 (en) 2008-10-24 2021-04-06 Ilumisys, Inc. Integration of LED lighting with building controls
US10932339B2 (en) 2008-10-24 2021-02-23 Ilumisys, Inc. Light and light sensor
US9585216B2 (en) 2008-10-24 2017-02-28 Ilumisys, Inc. Integration of LED lighting with building controls
US9398661B2 (en) 2008-10-24 2016-07-19 Ilumisys, Inc. Light and light sensor
US9635727B2 (en) 2008-10-24 2017-04-25 Ilumisys, Inc. Light and light sensor
US10036549B2 (en) 2008-10-24 2018-07-31 Ilumisys, Inc. Lighting including integral communication apparatus
US10342086B2 (en) 2008-10-24 2019-07-02 Ilumisys, Inc. Integration of LED lighting with building controls
US10560992B2 (en) 2008-10-24 2020-02-11 Ilumisys, Inc. Light and light sensor
WO2010064167A3 (fr) * 2008-12-04 2010-12-02 Koninklijke Philips Electronics N.V. Procédés de sélection et dispositifs de commande
CN102239747B (zh) * 2008-12-04 2014-03-26 皇家飞利浦电子股份有限公司 用于选择和控制设备的方法
US9578722B2 (en) 2008-12-04 2017-02-21 Philips Lighting Holding B.V. Methods for selecting and controlling devices
US9526149B2 (en) 2009-11-03 2016-12-20 Philips Lighting Holding B.V. Object-sensing lighting network and control system therefor
WO2011055259A1 (fr) * 2009-11-03 2011-05-12 Koninklijke Philips Electronics N.V. Réseau d'éclairage avec détection d'objet et système de commande associé
US9013119B2 (en) 2010-03-26 2015-04-21 Ilumisys, Inc. LED light with thermoelectric generator
US8840282B2 (en) 2010-03-26 2014-09-23 Ilumisys, Inc. LED bulb with internal heat dissipating structures
ITVI20100235A1 (it) * 2010-08-13 2012-02-14 St Microelectronics Srl Sistema di localizzazione per il monitoraggio dell'illuminazione stradale
US8731866B2 (en) 2010-08-13 2014-05-20 Stmicroelectronics S.R.L. Location system for street light monitoring
US9271367B2 (en) 2012-07-09 2016-02-23 Ilumisys, Inc. System and method for controlling operation of an LED-based light
US10966295B2 (en) 2012-07-09 2021-03-30 Ilumisys, Inc. System and method for controlling operation of an LED-based light
WO2014011497A1 (fr) * 2012-07-09 2014-01-16 Ilumisys, Inc. Système et procédé de commande du fonctionnement d'une lumière à del
US9807842B2 (en) 2012-07-09 2017-10-31 Ilumisys, Inc. System and method for controlling operation of an LED-based light
US9839102B2 (en) 2012-07-12 2017-12-05 Lg Innotek Co., Ltd. Lighting control method and lighting control system
EP2685793A1 (fr) * 2012-07-12 2014-01-15 LG Innotek Co., Ltd. Système et procédé de commande d'éclairage
US9439271B2 (en) 2012-07-12 2016-09-06 Lg Innotek Co., Ltd. Lighting control method and lighting control system
US9357621B2 (en) 2012-07-12 2016-05-31 Lg Innotek Co., Ltd. Lighting control apparatus, lighting control method, and lighting control system
US9949349B2 (en) 2012-07-12 2018-04-17 Lg Innotek Co., Ltd. Lighting control apparatus, lighting control method, and lighting control system
US9285084B2 (en) 2013-03-14 2016-03-15 Ilumisys, Inc. Diffusers for LED-based lights
US9574717B2 (en) 2014-01-22 2017-02-21 Ilumisys, Inc. LED-based light with addressed LEDs
US10260686B2 (en) 2014-01-22 2019-04-16 Ilumisys, Inc. LED-based light with addressed LEDs
US9510400B2 (en) 2014-05-13 2016-11-29 Ilumisys, Inc. User input systems for an LED-based light
US10690296B2 (en) 2015-06-01 2020-06-23 Ilumisys, Inc. LED-based light with canted outer walls
US10161568B2 (en) 2015-06-01 2018-12-25 Ilumisys, Inc. LED-based light with canted outer walls
US11028972B2 (en) 2015-06-01 2021-06-08 Ilumisys, Inc. LED-based light with canted outer walls
US11428370B2 (en) 2015-06-01 2022-08-30 Ilumisys, Inc. LED-based light with canted outer walls
EP3672335A1 (fr) * 2018-12-21 2020-06-24 Signify Holding B.V. Procédé et dispositif pour la mise en service d'un système d'éclairage
US11044797B2 (en) 2018-12-21 2021-06-22 Signify Holding B.V. Method of and device for commissioning a lighting system

Also Published As

Publication number Publication date
WO2008129488A3 (fr) 2008-12-18
TW200850056A (en) 2008-12-16

Similar Documents

Publication Publication Date Title
WO2008129488A2 (fr) Système et procédé pour le recalcul de probabilités dans des arbres de décision
JP4959729B2 (ja) 自動作動のための決定木の使用
US8290437B2 (en) Locating reference nodes for positioning devices in a wireless network
JP6067688B2 (ja) ネットワーク化された制御システムの装置の自動コミッショニング
JP5081167B2 (ja) ノードグループ化用位置の使用
JP5818779B2 (ja) フィンガープリント法を用いた位置検出システム及び位置検出方法
US20080157957A1 (en) Wall Finding For Wireless Lighting Assignment
US10470155B2 (en) Commissioning of an indoor positioning system using a secondary positioning system
US8520647B2 (en) Wireless client position estimating system and method
US20140175990A1 (en) Automatically commissioning lighting controls using sensing parameters of the lighting controls
CN108141943A (zh) 用于自动化的照明器材位置映射的系统和方法
CN110677272A (zh) 用于形成设备网络的方法及系统
WO2020114584A1 (fr) Procédé et système d'affectation de technicien permettant d'affecter un technicien de terrain
US10524138B2 (en) System for RF quiet channel optimization
EP3672335B1 (fr) Procédé et dispositif pour la mise en service d'un système d'éclairage
CN114442038B (zh) 一种室内定位方法、装置、存储介质及系统
JP2019220262A (ja) 照明システムコンポーネントを自動的に位置決めして管理する方法
CN117769004A (zh) 终端设备位置分配方法、装置、存储介质及电子设备

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 08763040

Country of ref document: EP

Kind code of ref document: A2

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 08763040

Country of ref document: EP

Kind code of ref document: A2