WO2023083577A1 - Procédé pour déterminer des positions optimisées d'un objet pour le suivi d'une trajectoire dans un environnement simulé. - Google Patents

Procédé pour déterminer des positions optimisées d'un objet pour le suivi d'une trajectoire dans un environnement simulé. Download PDF

Info

Publication number
WO2023083577A1
WO2023083577A1 PCT/EP2022/079206 EP2022079206W WO2023083577A1 WO 2023083577 A1 WO2023083577 A1 WO 2023083577A1 EP 2022079206 W EP2022079206 W EP 2022079206W WO 2023083577 A1 WO2023083577 A1 WO 2023083577A1
Authority
WO
WIPO (PCT)
Prior art keywords
point
trajectory
steps
main trajectory
candidate
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/EP2022/079206
Other languages
English (en)
Inventor
Sylvain CONTASSOT-VIVIER
Virgile DAUGE
Laurent CIARLETTA
Adrien GUENARD
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.)
Centre National de la Recherche Scientifique CNRS
Institut National Polytechnique de Lorraine
Institut National de Recherche en Informatique et en Automatique INRIA
Original Assignee
Centre National de la Recherche Scientifique CNRS
Institut National Polytechnique de Lorraine
Institut National de Recherche en Informatique et en Automatique INRIA
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 Centre National de la Recherche Scientifique CNRS, Institut National Polytechnique de Lorraine, Institut National de Recherche en Informatique et en Automatique INRIA filed Critical Centre National de la Recherche Scientifique CNRS
Publication of WO2023083577A1 publication Critical patent/WO2023083577A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0217—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory in accordance with energy consumption, time reduction or distance reduction criteria
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/20—Instruments for performing navigational calculations
    • G01C21/206—Instruments for performing navigational calculations specially adapted for indoor navigation
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0231—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means
    • G05D1/0246—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means using a video camera in combination with image processing means
    • G—PHYSICS
    • G08—SIGNALLING
    • G08B—SIGNALLING SYSTEMS, e.g. PERSONAL CALLING SYSTEMS; ORDER TELEGRAPHS; ALARM SYSTEMS
    • G08B13/00—Burglar, theft or intruder alarms
    • G08B13/18—Actuation by interference with heat, light, or radiation of shorter wavelength; Actuation by intruding sources of heat, light, or radiation of shorter wavelength
    • G08B13/189—Actuation by interference with heat, light, or radiation of shorter wavelength; Actuation by intruding sources of heat, light, or radiation of shorter wavelength using passive radiation detection systems
    • G08B13/194—Actuation by interference with heat, light, or radiation of shorter wavelength; Actuation by intruding sources of heat, light, or radiation of shorter wavelength using passive radiation detection systems using image scanning and comparing systems
    • G08B13/196—Actuation by interference with heat, light, or radiation of shorter wavelength; Actuation by intruding sources of heat, light, or radiation of shorter wavelength using passive radiation detection systems using image scanning and comparing systems using television cameras
    • G08B13/19639—Details of the system layout
    • G08B13/19645—Multiple cameras, each having view on one of a plurality of scenes, e.g. multiple cameras for multi-room surveillance or for tracking an object by view hand-over

Definitions

  • TITLE Method for determining optimized positions of an object for following a trajectory in a simulated environment.
  • the present invention relates to a method for determining optimized positions of at least one object provided with a field of vision for following a trajectory in a simulated environment comprising obstacles, the field of vision being able to be defined by a source, a range and an opening angle.
  • the invention applies in particular in the field of precise geolocation in areas not covered by conventional systems (GPS, radio signals, visual landmarks, etc.) such as the interiors of buildings, mines, but also other planets, which pose major difficulties for exploration and/or monitoring/maintenance tasks.
  • conventional systems GPS, radio signals, visual landmarks, etc.
  • a model of the environment is available or designed in such a way as to show passages and fixed elements such as walls, walls, posts, etc. It can be a model finished or yet to be developed.
  • a trajectory can be predefined in the environment for an exploration mission through passages avoiding any obstacle. To do this, provision is made to position the object at different locations in the environment for efficient tracking of a mobile element moving on the trajectory.
  • the object of the present invention is to determine optimized locations for positioning the object.
  • Another object of the invention is to minimize the calculation time for determining these locations.
  • Another object of the invention is to determine a minimum number of locations making it possible to cover the entire trajectory.
  • At least one of the aforementioned objectives is achieved with a method for determining optimized positions of at least one object provided with a field of vision for following a trajectory in a simulated environment comprising obstacles, the field of vision including a source, a range and an opening angle.
  • the method is implemented by a computer and comprises the following steps: a) selection of a set of candidate positions, b) for each candidate position, construction of a local field of vision placed at this position candidate and oriented according to the following steps: bl) definition of two vectors positioned at the candidate position and oriented towards a first point of a segment of the main trajectory, this first point being within range of the object when the object is placed at the candidate position, b2) scanning point by point of the segment; at each new scanned point of the segment, the vectors point to two scanned points furthest apart from the candidate position, b3) end of scanning when a new scanned point is considered invalid; a scanned point being considered invalid when this scanned point is out of range or the angle formed by the two vectors is greater than the opening angle of the field of view or an obstacle is in the triangle formed by the position candidate, the previous scanned point and the new scanned point; the local field of view being defined by the range of the field of view and an opening angle formed by the two vectors
  • the method according to the invention makes it possible, for candidate positions, to effectively orient local fields of vision.
  • the overall construction makes it possible to retain a minimum of position to cover the entire trajectory. Therefore, a mobile moving along the main trajectory can be fully tracked from the optimized positions.
  • the field of vision can be formalized in the form of a circular sector, that is to say a disk sector defined by an opening angle and a radius equal to the range of the object.
  • step a) of selecting a set of candidate positions can comprise the following steps:
  • minimum safety distance is meant a minimum distance determined according to the size of the element which must follow the trajectory.
  • the left and right paths are thus constrained not directly by the obstacles but by safety zones around the obstacles.
  • the perpendicular to the trajectory is deduced from the approximate tangent of the main trajectory, and corresponds to the normal to the trajectory at the point considered.
  • all of the candidate positions can be positioned on suitable left and right paths. These paths make it possible to guarantee that the object will be placed mainly at the same distance optimized for tracking a mobile on the trajectory.
  • the distance between the main trajectory and the left path or the right path can be determined by carrying out the following steps:
  • the distance between the main trajectory and the left or right path is defined as being equal to a height between the source and the middle of the tolerance band.
  • the method according to the invention therefore makes it possible to provide an optimized distance between the object and the trajectory so as to cover a maximum length of the trajectory at each position.
  • the tolerance band is a margin of tolerance of the distance between the object and the trajectory. That is to say that, for an object positioned and oriented facing the trajectory, as long as the variations of the trajectory remain within this margin, it is considered that the field of vision covers a segment of the acceptable trajectory.
  • step a) of selecting a set of candidate positions may also comprise the following steps:
  • Said reserved zone corresponds to a zone reserved for the mobile element to be followed.
  • the selection of a part of the points of the differential zones is obtained during each step d1) of determining a candidate position having the highest score; said set of candidate positions further comprising candidate positions obtained according to the following steps: dll) identification of parts of the differential zones located within range of said end of the main trajectory; for each part identified, carrying out the following steps: d12) sampling at one resolution, dl3) evaluation by calculating a score for each point obtained after sampling, dl4) selection of the best point, dl5) determination of a limited zone around the best selected point, d16) repeating steps d12) to d15) with said resolution increasing at each repetition until a predetermined level of resolution is reached, then selecting the last best point as candidate position.
  • the method according to the invention makes it possible to search for candidate positions in parts of the differential zones. To do this, at the same time as the trajectory is traversed during the global construction phase, the number of candidate positions is increased by considering the points within reach of the first of each trajectory segment. The candidate position that will be retained is the one with the best score.
  • limited zone is meant a zone of dimension less than the dimension of the identified part, for example this limited zone can be delimited by the nearest neighbors of the selected point.
  • the selection of a part of the points in a differential zone can comprise the following steps: dl2) sampling at one resolution, dl3) evaluation by calculating a score for each point obtained after sampling, dl4 ) selection of the best point, dl5) determination of a limited zone around the best point selected, d16) repetition of steps d12) to d15) with increase of said resolution at each repetition until reaching a predetermined level of resolution, then selection of the last best point as candidate position.
  • each differential zone can be divided into several differential sub-zones comprising several sampled points. Furthermore, steps d12) to d15) can then be carried out on each of the differential sub-zones thus cut out.
  • the candidate positions on the differential zones can be obtained independently and upstream of the overall construction phase.
  • the advantage of carrying out multi-samplings on small surfaces is to reduce the cost of the calculations compared to a high-resolution sampling on all the differential zones.
  • the points of the main trajectory can be determined by random, systematic sampling, in particular at regular intervals, or according to a predetermined rule.
  • the score can be a length of the segment scanned or the number of points scanned.
  • the object is an electronic detection device. It can be a laser, a camera, a stand to be placed along a racing circuit, etc.
  • the invention also relates to a computer program product comprising instructions which, when the program is executed by a computer, lead the latter to implement the steps of the method as defined above.
  • Figure 1 is a schematic view of a model of the environment
  • Figure 2 is a schematic view of several models representing the field of vision of a headlight, with 6 varying
  • Figure 3 is a diagram illustrating a principle for determining a tolerance band
  • Figure 4 is a schematic view for comparing band widths as defined in Figure 3,
  • Figure 5 is a schematic view illustrating ideal paths, represented in the environment
  • Figure 6 is a schematic view illustrating paths adapted to the environment, undersampled trajectory,
  • Figure 7 is a schematic view illustrating adapted trails calculated using all points
  • Figure 8 is a schematic view illustrating a process for determining the local field of view
  • Figure 9 is a schematic view illustrating a succession of local optimization steps constituting a global solution
  • Figure 10 is a schematic view illustrating a global solution obtained from the paths
  • Figure 11 is a schematic view illustrating a reserved area around two segments of the trajectory and the generation of a surface of solutions around two distinct points
  • Figure 12 is a schematic view illustrating regular sampling and local optimization
  • Figure 13 is a schematic view illustrating progressive sampling
  • FIG. 14 is a schematic view illustrating a succession of local steps passing from segment to segment of the trajectory with progressive sampling of each surface covered by the local field of vision.
  • the various embodiments of the present invention include various steps. These steps can be implemented by instructions of an executable machine by means of a microprocessor for example.
  • these steps can be performed by specific integrated circuits including hard-wired logic to perform the steps, or by any combination of programmable components and custom components.
  • the present invention may also be provided in the form of a computer program product which may comprise a non-transitory computer memory medium containing instructions executable on a computer machine, these instructions being able to be used to program a computer (or any other device electronics) to perform the process.
  • a method according to the invention for determining the positions of a laser detector for tracking the trajectory of a robot in a simulated environment.
  • This laser detector is subsequently called a beacon. It can be any type of device with which a field of vision can be associated. Mention may also be made of a drone equipped with a detection and/or display means.
  • FIG. 1 is a schematic view of an environment model representing walls 1 and posts 2.
  • the empty spaces are passages through which one or more trajectories can be envisaged.
  • the present invention relates to a headlight placement strategy, so as to optimize, here minimize, the number of headlight positions necessary to carry out a given task.
  • the mission can be the exploration of the environment by two robots or drones, one serving as a beacon placed successively in optimized positions to visualize the course of the second.
  • the objective of the invention is to determine the positions of the headlights in a simulated environment in order then to deduce therefrom a positioning of said headlights in the real environment.
  • the positions that will be determined have a technical effect in tracking a mobile on a trajectory in the real environment.
  • a solution to the global problem is a list of pairs (placement, section) describing how to position the lighthouse and which section of the trajectory is covered by the so positioned lighthouse:
  • Solution [ placemento, sectiono) , . . . placement,,, section,,)
  • optimization at the global level therefore consists in minimizing the number n of pairs necessary for carrying out the mission.
  • each step is dependent on the previous one, the starting point of the section k+i being the last point of the section /,.
  • the global optimum can be obtained by successively selecting the best local solutions. That is to say, choose the placement of the headlight that allows you to maximize the section of trajectory covered, then loop on the rest of the trajectory.
  • the present invention makes it possible in particular to determine the space of local solutions, which is in reality a set of possible placements of the lighthouse, to calculate the relevance of each of these solutions in the form of a score determined analytically so as to select the best placement, then to build the global solution covering the entire trajectory.
  • the area covered can be defined by various elements:
  • the range p distance in meters at which the receivers are still capable of capturing and using the information encoded in the lasers
  • angle 6 angle delimiting the field of vision, expressed in degrees or in radians
  • the coverage area of a lighthouse is a circular sector, defined by the following inequalities: x 2 + y 2 ⁇ p 2 -tan (0/2) ⁇ x/y ⁇ tan 6/2) y > 0
  • the trajectory is mainly rectilinear, the variations of directions, that is to say the bends, being only particular cases between two rectilinear sections.
  • the opening angle is small: 6 ⁇ 60°
  • c reaches more than 9.5m, whereas the range of the headlight is only 5m.
  • Placing the lighthouse so as to superimpose the chord c of the circular sector therefore makes it possible to maximize the length of rectilinear trajectory covered by the lighthouse. And therefore, at the same time, to minimize the number of headlight movements necessary for the proper conduct of a mission.
  • the choice of the bandwidth b can be a compromise between maximum length covered and maximum area covered.
  • FIG. 5 is represented a main trajectory 51.
  • the headlights must be placed in positions optimized to cover the whole of this main trajectory 51.
  • This main trajectory may have been determined in particular during a trajectory generation process involving dotted paths in figure 5.
  • each path is a virtual trajectory parallel to the main trajectory, offset by a constant distance from the headlight to the left or to the right.
  • the left or right side is a simple representation to specify that the paths are arranged on either side of the main trajectory in a 2D representation of the simulated environment, seen from above.
  • a path is the set of possible solutions to the problem of optimizing the placement of headlights respecting the distance criterion defined above.
  • Determining a path parallel to the main trajectory requires some geometric calculations, mostly located in the determination of the interior turns of the curve.
  • a computer module such as for example Shapely offers a convenience function allowing these calculations to be carried out automatically.
  • the present invention proposes a new algorithm making it possible to achieve the same result using only set operations.
  • We are going to construct a perpendicular bisector M for each pair ti, t/'+1) of consecutive points of the main trajectory.
  • the left halves M g and right Md of this perpendicular bisector will play the role of rays.
  • the restricted zones as well as the ideal paths S g (left) and Sd (right) previously determined will play the role of limits on which the rays will stop.
  • I d ⁇ m £ M d Wz £ Z, m Cl (z US d ) 0 ⁇ It is then a matter of determining the point p included in Id closest to the origin of the half-bisector Md.
  • Figure 5 illustrates the algorithm with two examples on an undersampled trajectory, thus allowing to draw the constructed rays without saturating the image.
  • the set Id may contain only one point, the perpendicular bisector not crossing any obstacles, in which case this point will be used to construct the adapted path. This is the simplest case, visible for the right semi-bisector between t38 and t39.
  • This set can also contain a point and a set of segments resulting from the intersection between the restricted zones and the semi-mediator. It will then be necessary to select the point closest to the origin of the half-bisector among the set of points included in these intersection segments. This is the case for the right half-bisector of points t36 and t37.
  • Figure 6 illustrates a result when the algorithm is applied on a correctly sampled main trajectory.
  • the left 71 and right 72 matched paths in FIG. 7 therefore constitute the set of candidate positions for the lighthouse. It is then a question of determining the orientation of the lighthouse in each candidate position by constructing a local field of vision.
  • the present invention provides an analytical determination of the orientation of the headlight. To do this, this determination is made during an evaluation phase during which each candidate position is evaluated.
  • Figure 8 presents different stages of the enlargement of the virtual circular sector.
  • the Umin and Umax vectors are updated as needed, each adding point tk, if the point is outside the circular sector. If there is an update, it is verified that the opening angle ⁇ of the virtual sector is still less than the maximum angle permitted by the headlight.
  • the distance between the point to be added and the candidate position of the lighthouse is also calculated. If the two conditions 6 ⁇ Qmax and ll - tdl ⁇ range are met, it is possible to cover tk from p.
  • the environment model comprises a set O of polygons representing the obstacles (walls, posts, etc.).
  • the evaluation strictly speaking consists in calculating a score for each determined local field of vision.
  • the score is proportional to the segment taken in the local field of view. We can directly calculate this distance by gradually summing the distances lltk-i - t/dl, or simply by counting the number of points covered, which is less costly and also discriminating for the choice of the optimal solution.
  • the evaluation phase therefore allows for each candidate position to construct a local field of vision and to associate a score with it.
  • an optimal global solution consists in solving the local covered trajectory maximization problem starting from the beginning of the trajectory.
  • the candidate position is retained whose local field of vision integrates the first point of the main trajectory and presents the highest score (among all the fields of vision integrating the first point of the main trajectory). It is then necessary to reduce the trajectory to be processed by subtracting the part covered previously. We loop in this way as long as there are still points in the trajectory to process.
  • FIG. 9 makes it possible to visualize the various steps necessary to follow the main trajectory from end to end. Locally assessed points and their associated scores are drawn on each step. The optimal solution is chosen among these points allowing at the same time to determine the covered section. This solution is represented by the circular sector of diffusion in figure 9. This process is then repeated until the end of the trajectory.
  • the local field of vision 91 can be distinguished, the source of which is located against a wall of the environment on a suitable path.
  • the source of the field of view coincides with a candidate position 92 having had the highest score among a set of candidate positions in the range of the starting point 93.
  • the candidate position 92 which was selected is on the left path.
  • the opening angle of this local field of vision is less than or equal to the maximum field of vision of the headlight.
  • the segment or section covered by the field of view is as large as possible.
  • step 1 we consider the rest of the main trajectory.
  • the starting point is now the first point of the rest of the path not covered by the first segment.
  • the position having obtained the best score is considered.
  • the local field of vision of this position makes it possible to determine the covered segment.
  • the algorithm is applied successively on the rest of the trajectory until reaching the end point, 94 in step 4 in Figure 9.
  • the global solution thus obtained is summarized in figure 10, where the successive steps are superimposed on the map, forming an optimal solution.
  • the relevance of this solution is assessed by the number of steps necessary to carry out the mission.
  • the present invention thus proposes solutions for which the candidate positions are on the appropriate paths. This is optimal for a purely straight trajectory. However, in many practical cases, the trajectory to be followed is far from straight. To do this, the present invention provides for extending the space of solutions to the entire surface between the left and right paths so as to better cover the sections with strong curvature. Increasing the space of solutions in this way obviously has a computational cost, but can make it possible to obtain better solutions with respect to positions on the paths.
  • a surface Sk is first determined as being the surface of the optimized detection zone. Moreover, since the lighthouse must not interfere with the mobile in following its main trajectory, we discard the points that are too close to the latter.
  • Rk denote this reserved area, which is defined by the constraint of compliance with the safety distance ds as follows:
  • FIG. 11 presents the surfaces and reserved zones 110 and 111 of two distinct sections of the main trajectory.
  • the set Pk of solutions for a section k will be defined by the difference between these two surfaces:
  • the Pk surface is a larger solution space than the previous paths and probably offers better local solutions.
  • the local solution found is better, because the chosen point covers a longer portion of the main trajectory.
  • the total cost of the optimization increases linearly with the number of points tested.
  • a rapid quantitative and qualitative analysis allows the validation of the approach, which makes it possible to obtain such precise results. It is even possible, in view of the reduction in computational cost, to compute at a higher resolution, which would take too much time in practice for the single-scale approach.

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • Automation & Control Theory (AREA)
  • General Physics & Mathematics (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Multimedia (AREA)
  • Electromagnetism (AREA)
  • Image Analysis (AREA)

Abstract

L'invention concerne un procédé pour déterminer des positions optimisées d'au moins un objet doté d'un champ de vision pour le suivi d'une trajectoire dans un environnement simulé comprenant des obstacles, le champ de vision comprenant une source, une portée et un angle d'ouverture. Le procédé est mis en oeuvre par un ordinateur et comprend les étapes suivantes : a) sélection d'un ensemble de positions candidates, b) pour chaque position candidate, construction d'un champ de vision local placé à cette position candidate et orienté de façon à englober un segment le plus grand possible, c) affectation d'un score à chaque position candidate, d) parcours de la trajectoire principale segment par segment en sélectionnant pour chaque segment une position candidate ayant un score le plus élevé.

Description

DESCRIPTION
TITRE : Procédé pour déterminer des positions optimisées d'un objet pour le suivi d'une trajectoire dans un environnement simulé.
La présente invention concerne un procédé pour déterminer des positions optimisées d'au moins un objet doté d'un champ de vision pour le suivi d'une trajectoire dans un environnement simulé comprenant des obstacles, le champ de vision pouvant être défini par une source, une portée et un angle d'ouverture.
L'invention s'applique notamment dans le domaine de géolocalisation précise dans des zones non couvertes par les systèmes classiques (GPS, signaux radio, amers visuels...) telles que les intérieurs de bâtiments, les mines, mais aussi les autres planètes, qui posent des difficultés majeures pour les tâches d'exploration et/ou de surveillance/maintenance.
D'une façon générale, un modèle de l'environnement est disponible ou conçu de façon à faire apparaître des passages et des éléments fixes comme par exemple des parois, murs, poteaux, .... Il peut s'agir d'un modèle fini ou encore à élaborer. Une trajectoire peut être prédéfinie dans l'environnement pour une mission d'exploration à travers des passages en évitant tout obstacle. Pour ce faire, il est prévu de positionner l'objet sur différents emplacements dans l'environnement pour un suivi efficace d'un élément mobile se déplaçant sur la trajectoire.
La présente invention a pour but de déterminer des emplacements optimisés pour positionner l'objet.
Un autre but de l'invention est de minimiser le temps de calcul pour déterminer ces emplacements.
L'invention a encore pour but la détermination d'un nombre minimum d'emplacements permettant de couvrir l'ensemble de la trajectoire.
On atteint au moins l'un des objectifs précités avec un procédé pour déterminer des positions optimisées d'au moins un objet doté d'un champ de vision pour le suivi d'une trajectoire dans un environnement simulé comprenant des obstacles, le champ de vision comprenant une source, une portée et un angle d'ouverture. Selon l'invention, le procédé est mis en œuvre par un ordinateur et comprend les étapes suivantes : a) sélection d'un ensemble de positions candidates, b) pour chaque position candidate, construction d'un champ de vision local placé à cette position candidate et orienté suivant les étapes suivantes : bl) définition de deux vecteurs positionnés à la position candidate et orientés vers un premier point d'un segment de la trajectoire principale, ce premier point étant à la portée de l'objet lorsque l'objet est placé à la position candidate, b2) balayage point par point du segment ; à chaque nouveau point balayé du segment, les vecteurs pointent vers deux points balayés les plus écartés vis-à-vis de la position candidate, b3) fin de balayage lorsqu'un nouveau point balayé est considéré non valide ; un point balayé étant considéré non valide lorsque ce point balayé se trouve hors de portée ou l'angle formé par les deux vecteurs est supérieur à l'angle d'ouverture du champ de vision ou un obstacle se trouve dans le triangle formé par la position candidate, le précédent point balayé et le nouveau point balayé; le champ de vision local étant défini par la portée du champ de vision et un angle d'ouverture formé par les deux vecteurs pour le dernier point balayé valide, c) affectation d'un score à chaque position candidate, d) construction globale des positions optimisées en réalisant les étapes suivantes : dl) à partir d'une extrémité de la trajectoire principale, détermination d'une position candidate ayant le score le plus élevé parmi un ensemble de positions candidates ayant un champ de vision local couvrant ledit point de départ ; le champ de vision local de la position candidate ainsi déterminée couvrant un segment de la trajectoire principale, d2) application successive de l'étape précédente sur le reste de la trajectoire principale jusqu'à ce qu'un champ de vision local couvre une autre extrémité de la trajectoire principale, d3) sauvegarde de l'ensemble des positions candidates ainsi déterminées comme étant les positions optimisées pour le placement dudit objet. Le procédé selon l'invention permet, pour des positions candidates, d'orienter des champs de vision locaux de façon efficace. La construction globale permet de retenir un minimum de position pour couvrir l'ensemble de la trajectoire. De ce fait, un mobile se déplaçant le long de la trajectoire principale peut totalement être suivi depuis les positions optimisées. Selon l'invention, il est prévu d'avoir plusieurs objets, chacun disposé à une position optimisée, ou bien d'avoir au moins un objet apte à se déplacer sur plusieurs positions optimisées en fonction du déplacement dudit mobile sur la trajectoire.
Le champ de vision peut être formalisé sous la forme d'un secteur circulaire, c'est-à-dire un secteur de disque défini par un angle d'ouverture et un rayon égal à la portée de l'objet.
Selon une caractéristique avantageuse de l'invention, l'étape a) de sélection d'un ensemble de positions candidates peut comprendre les étapes suivantes :
- détermination d'une zone de détection optimisée le long de la trajectoire principale, cette zone étant délimitée par une trajectoire virtuelle gauche, dite sentier gauche, et une trajectoire virtuelle droite, dite sentier droit, les deux trajectoires virtuelles étant à une distance fixe de la trajectoire principale,
- pour tout point de la trajectoire principale, détermination d'une position candidate disposée perpendiculairement à la trajectoire principale et située sur le sentier gauche ou à une distance minimale de sécurité d'un obstacle si cet obstacle se trouve entre le sentier gauche et le point de la trajectoire principale,
- pour tout point de la trajectoire principale, détermination d'une position candidate disposée perpendiculairement à la trajectoire principale et située sur le sentier droit ou à une distance minimale de sécurité d'un obstacle si cet obstacle se trouve entre le sentier droit et le point de la trajectoire principale.
Par distance minimale de sécurité, on entend une distance minimale déterminée en fonction de la taille de l'élément qui doit suivre la trajectoire. De préférence, les sentiers gauche et droit sont ainsi contraints non pas directement par les obstacles mais par des zones de sécurité autour des obstacles.
La perpendiculaire à la trajectoire est déduite de la tangente approchée de la trajectoire principale, et correspond à la normale à la trajectoire au point considéré. Avec l'invention, l'ensemble des positions candidates peut être positionné sur des sentiers gauche et droite adaptés. Ces sentiers permettent de garantir le fait que l'objet sera placé majoritairement à une même distance optimisée pour le suivi d'un mobile sur la trajectoire.
En complément notamment de tout ce qui précède, la distance entre la trajectoire principale et le sentier gauche ou le sentier droit peut être déterminée en réalisant les étapes suivantes :
- détermination d'une corde C du champ de vision comme étant la distance maximum d'un segment inscrit dans le champ de vision,
- détermination d'une bande de tolérance comprenant la corde C, la distance entre la trajectoire principale et le sentier gauche ou droit est définie comme étant égale à une hauteur entre la source et le milieu de la bande de tolérance.
Le procédé selon l'invention permet donc de prévoir une distance optimisée entre l'objet et la trajectoire de façon à couvrir un maximum de longueur de la trajectoire à chaque position. La bande de tolérance est une marge de tolérance de la distance entre l'objet et la trajectoire. C'est-à-dire que, pour un objet positionné et orienté face à la trajectoire, tant que les variations de la trajectoire restent dans cette marge, l'on considère que le champ de vision couvre un segment de la trajectoire acceptable.
En complément notamment de tout ce qui précède, l'étape a) de sélection d'un ensemble de positions candidates peut en outre comprendre les étapes suivantes :
- détermination d'une zone réservée autour de la trajectoire principale, cette zone réservée étant moins large que la zone de détection optimisée ; des espaces obtenus entre la zone de détection optimisée et la zone réservée constituant des zones différentielles, et
- sélection de tout ou partie des points des zones différentielles comme des positions candidates.
Ladite zone réservée correspond à une zone réservée à l'élément mobile à suivre.
Il s'agit là d'un moyen pour obtenir plus de positions candidates non pas sur les sentiers mais également sur des surfaces qui sont plus proches de la trajectoire tout en conservant une distance minimum de sécurité représentée par la zone réservée. En complément notamment de ce qui précède, la sélection d'une partie des points des zones différentielles est obtenue lors de chaque étape dl) de détermination d'une position candidate ayant le score le plus élevé ; ledit ensemble de positions candidates comprenant en outre des positions candidates obtenues selon les étapes suivantes : dll) identification de parties des zones différentielles se trouvant à portée de la dite extrémité de la trajectoire principale ; pour chaque partie identifiée, réalisation des étapes suivantes : d 12) échantillonnage à une résolution, dl3) évaluation en calculant un score pour chaque point obtenu après échantillonnage, dl4) sélection du meilleur point, dl5) détermination d'une zone limitée autour du meilleur point sélectionné, dl6) répétition des étapes dl2) à dl5) avec augmentation de ladite résolution à chaque répétition jusqu'à atteindre un niveau de résolution prédéterminé, puis sélection du dernier meilleur point comme position candidate.
Le procédé selon l'invention permet de rechercher des positions candidates dans des parties des zones différentielles. Pour ce faire, en même temps que l'on parcourt la trajectoire lors de la phase de construction globale, on augmente le nombre de positions candidates en considérant les points à la portée du premier de chaque segment de trajectoire. La position candidate qui sera retenue est celle qui présentera le meilleur score.
Par zone limitée on entend une zone de dimension inférieure à la dimension de la partie identifiée, par exemple cette zone limitée peut être délimitée par les plus proches voisins du point sélectionné.
Selon un mode de réalisation de l'invention, la sélection d'une partie des points dans une zone différentielle peut comprendre les étapes suivantes : dl2) échantillonnage à une résolution, dl3) évaluation en calculant un score pour chaque point obtenu après échantillonnage, dl4) sélection du meilleur point, dl5) détermination d'une zone limitée autour du meilleur point sélectionné, dl6) répétition des étapes dl2) à dl5) avec augmentation de ladite résolution à chaque répétition jusqu'à atteindre un niveau de résolution prédéterminé, puis sélection du dernier meilleur point comme position candidate.
En complément notamment de ce qui précède, chaque zone différentielle peut être découpée en plusieurs sous-zones différentielles comprenant plusieurs points échantillonnés. Par ailleurs, les étapes dl2) à dl5) peuvent alors être réalisées sur chacune des sous-zones différentielles ainsi découpées.
Dans ce mode de réalisation, les positions candidates sur les zones différentielles peuvent être obtenues indépendamment et en amont de la phase de construction globale.
L'avantage de réaliser des multi-échantillonnages sur de petites surfaces est de diminuer le coût des calculs par rapport à un échantillonnage haute résolution sur toutes les zones différentielles.
Selon une caractéristique avantageuse de l'invention, les points de la trajectoire principale peuvent être déterminés par échantillonnage aléatoire, systématique, notamment à intervalle régulier, ou selon une règle prédéterminée.
Selon l'invention, le score peut être une longueur du segment balayé ou le nombre de points balayés.
Selon un mode de réalisation préféré, l'objet est un dispositif électronique de détection. Il peut s'agir d'un laser, une caméra, une tribune à disposer le long d'un circuit automobile, etc.
Il est également prévu un système de traitement de données comprenant des moyens pour mettre en œuvre les étapes du procédé tel que défini ci-dessus.
L'invention concerne également un produit programme d'ordinateur comprenant des instructions qui, lorsque le programme est exécuté par un ordinateur, conduisent celui-ci à mettre en œuvre les étapes du procédé tel que défini ci-dessus. D'autres avantages et caractéristiques de l'invention apparaîtront à l'examen de la description détaillée d'un mode de mise en œuvre nullement limitatif, et des dessins annexés, sur lesquels :
[Fig. 1] La figure 1 est une vue schématique d'un modèle de l'environnement, [Fig. 2] La figure 2 est une vue schématique de plusieurs modèles représentant le champ de vision d'un phare, avec 6 variant,
[Fig. 3] La figure 3 est une schématique illustrant un principe de détermination d'une bande de tolérance,
[Fig. 4] La figure 4 est une vue schématique permettant de comparer des largeurs de bandes comme définies sur la figure 3,
[Fig. 5] La figure 5 est une vue schématique illustrant des sentiers idéaux, représentés dans l'environnement,
[Fig. 6] La figure 6 est une vue schématique illustrant des sentiers adaptés à l'environnement, trajectoire sous-échantillonnée,
[Fig. 7] La figure 7 est une vue schématique illustrant des sentiers adaptés calculés en utilisant tous les points,
[Fig. 8] La figure 8 est une vue schématique illustrant un processus pour déterminer le champ de vision local,
[Fig. 9] La figure 9 est une vue schématique illustrant une succession d'étapes d'optimisations locales constituant une solution globale,
[Fig. 10] La figure 10 est une vue schématique illustrant une solution globale obtenue à partir des sentiers,
[Fig. 11] La figure 11 est une vue schématique illustrant une zone réservée autour de deux segments de la trajectoire et la génération d'une surface de solutions autour de deux points distincts,
[Fig. 12] La figure 12 est une vue schématique illustrant un échantillonnage régulier et une optimisation locale,
[Fig. 13] La figure 13 est une vue schématique illustrant un échantillonnage progressif,
[Fig. 14] La figure 14 est une vue schématique illustrant une succession d'étapes locales en passant de segment en segment de la trajectoire avec un échantillonnage progressif de chaque surface couverte par le champ de vision local.
Les modes de réalisation qui seront décrits dans la suite ne sont nullement limitatifs; on pourra notamment mettre en œuvre des variantes de l'invention ne comprenant qu'une sélection de caractéristiques décrites par la suite isolées des autres caractéristiques décrites, si cette sélection de caractéristiques est suffisante pour conférer un avantage technique ou pour différencier l'invention par rapport à l'état de la technique antérieur. Cette sélection comprend au moins une caractéristique de préférence fonctionnelle sans détails structurels, ou avec seulement une partie des détails structurels si cette partie uniquement est suffisante pour conférer un avantage technique ou pour différencier l'invention par rapport à l'état de la technique antérieur.
En particulier toutes les variantes et tous les modes de réalisation décrits sont prévus pour être combinés entre eux dans toutes les combinaisons où rien ne s'y oppose sur le plan technique.
Les différents modes de réalisation de la présente invention comprennent diverses étapes. Ces étapes peuvent être mises en œuvre par des instructions d'une machine exécutable au moyen d'un microprocesseur par exemple.
Alternativement, ces étapes peuvent être réalisées par des circuits intégrés spécifiques comprenant une logique câblée pour exécuter les étapes, ou par toute combinaison de composants programmable et composants personnalisés.
La présente invention peut également être fournie sous forme d'un produit programme d'ordinateur qui peut comprendre un support mémoire informatique non-transitoire contenant des instructions exécutables sur une machine informatique, ces instructions pouvant être utilisées pour programmer un ordinateur (ou tout autre dispositif électronique) pour exécuter le procédé.
Bien que l'invention n'y soit pas limitée, nous allons maintenant décrire un procédé selon l'invention pour déterminer les positions d'un détecteur laser pour le suivi de la trajectoire d'un robot dans un environnement simulé. Ce détecteur laser est par la suite nommé phare. Il peut s'agir de tout type de dispositif auquel un champ de vision peut être associé. On peut par ailleurs citer un drone équipé d'un moyen de détection et/ou de visualisation.
La figure 1 est une vue schématique d'un modèle d'environnement représentant des parois 1 et des poteaux 2. Les espaces vides sont des passages par lesquels une ou plusieurs trajectoires peuvent être envisagées.
La présente invention concerne une stratégie de placement des phares, de manière à optimiser, ici minimiser, le nombre de positions des phares nécessaire à la réalisation d'une mission donnée. La mission peut être l'exploration de l'environnement par deux robots ou drones, l'un servant de phare placé successivement dans des positions optimisées pour visualiser le parcours du second.
L'objectif de l'invention est de déterminer les positions des phares dans un environnement simulé pour ensuite en déduire un positionnement desdits phares dans l'environnement réel. Les positions qui seront déterminées ont un effet technique dans le suivi d'un mobile sur une trajectoire dans l'environnement réel.
Une solution au problème global est une liste de couples (placement, section) décrivant comment positionner le phare et quelle section de la trajectoire est couverte par le phare ainsi positionné :
Solution = [ placemento, sectiono) , . . . placement,,, section,,)
L'optimisation au niveau global consiste donc à minimiser le nombre n de couples nécessaires à la réalisation de la mission. Cependant, chaque étape est dépendante de la précédente, le point de départ de la sectionk+i étant le dernier point de la section/,.
L'optimal global peut être obtenu en sélectionnant successivement les meilleures solutions locales. C'est-à-dire choisir le placement du phare qui permet de maximiser la section de trajectoire couverte, puis boucler sur le reste de la trajectoire.
La présente invention permet notamment de déterminer l'espace de solutions locales, qui est en réalité un ensemble de placements possibles du phare, de calculer la pertinence de chacune de ces solutions sous la forme d'un score déterminé analytiquement de façon à sélectionner le meilleur placement, puis de construire la solution globale couvrant toute la trajectoire.
Pour un phare émettant un laser dans l'environnement, la zone couverte peut être définie par divers éléments :
- la portée p : distance en mètres à laquelle les récepteurs sont encore capables de capter et d'exploiter les informations encodées dans les lasers,
- angle 6 : angle délimitant le champ de vision, exprimé en degrés où en radians
Ainsi, la zone de couverture d'un phare est un secteur circulaire, défini par les inéquations suivantes : x2 + y2 < p2 -tan (0/2) < x/y < tan 6/2) y > 0
La figure 2 présente le modèle d'un phare, ou plutôt trois déclinaisons de ce modèle, avec une portée identique p = 5m mais avec différentes valeurs de l'angle d'ouverture 6. Lors d'une exploration typique, la trajectoire est majoritairement rectiligne, les variations de directions, c'est-à-dire les virages, n'étant que des cas particuliers entre deux sections rectilignes. En faisant l'hypothèse d'une trajectoire rectiligne, il devient alors aisé de déterminer comment placer le phare par rapport à la trajectoire. Ainsi, lorsque l'angle d'ouverture est petit : 6 < 60°, le plus grand segment inclus dans la zone de couverture est n'importe lequel des rayons du secteur circulaire, de longueur p, c'est le cas de l'exemple représenté avec 6 = 40°.
Dans le cas où 6 = 60°, la corde c et les deux rayons extrêmes délimitant le secteur circulaire forment un triangle équilatéral, donnant donc c = p. Enfin, dans le dernier cas, où 6 > 60° le plus grand segment inclus dans le secteur devient la corde c. Sa longueur est calculable en évaluant l'équation suivante c = 2p. si n (0/2)
Dans l'exemple de la figure 2, c atteint plus de 9.5m, alors que la portée du phare n'est que de 5m. Placer le phare de manière à superposer la corde c du secteur circulaire permet donc de maximiser la longueur de trajectoire rectiligne couverte par le phare. Et donc, par la même occasion, de minimiser le nombre de déplacements de phare nécessaires à la bonne conduite d'une mission. Afin d'effectuer cette superposition, il convient de placer le phare, orienté perpendiculairement à la direction de la trajectoire, à une distance d de cette dernière, calculée de la manière suivante : d = p.cos(0/2)
Cependant, même en dehors des virages, les trajectoires sont rarement parfaitement rectilignes, mais plutôt contenues dans une bande réduite, dont la largeur varie selon le scénario et l'intensité du lissage. Ainsi, modéliser la trajectoire par une bande de largeur b permet de mieux prendre en compte les réalités du terrain. La figure 3 représente cette bande, inscrite dans le secteur circulaire. Elle est définie entre une bordure intérieure, la corde c (à distance d du phare) et une bordure extérieure, la corde c' (à une distance d' = d + b du phare).
Augmenter la largeur b de la bande aura pour conséquence de diminuer la longueur maximale de bande couverte, à l'avantage de la capacité à mieux couvrir les cas où la trajectoire ne serait pas totalement rectiligne, ainsi que les virages bruts de la trajectoire. Cette capacité de tolérance est proportionnelle à l'aire de la bande, qui est définie de la manière suivante :
Figure imgf000013_0001
Le choix de la largeur de bande b peut être un compromis entre longueur maximale couverte et aire maximale couverte. L'évaluation de ces grandeurs en fonction de la largeur de bande est présentée sur la figure 4, qui propose un compromis déterminé par l'intersection des courbes distance (décroissante) et aire (croissante) exprimées dans la même échelle. Sur la figure 4, l'intersection correspond à la valeur de b = 2.25m, ce qui donne un c' = 7.06m.
On prévoit de placer le phare orienté en direction de la trajectoire à une distance constante. Cette distance est déterminée en additionnant la distance d définie précédemment (entre le phare et la bordure intérieure) et la moitié de la largeur de bande. Ainsi : dphare = p.cos(0/2) +b/2
Dans le cas présent, pour Q =150°, b=2.25m et p=5m, on obtient une distance de dphare = 2.418m.
Sur la figure 5 est représentée une trajectoire principale 51. Les phares doivent être placés dans des positions optimisées pour couvrir l'ensemble de cette trajectoire principale 51. Cette trajectoire principale peut avoir notamment été déterminée lors d'un processus de génération de trajectoire faisant intervenir des allées en pointillées sur la figure 5.
Pour tenir compte de la distance dphare dans le positionnement du phare, on peut définir une nouvelle trajectoire de chaque côté de la trajectoire principale, que nous nommerons sentiers. Chaque sentier est une trajectoire virtuelle parallèle à la trajectoire principale, décalée d'une distance constante dphare vers la gauche ou vers la droite. Le côté gauche ou droit est une simple représentation pour spécifier que les sentiers sont disposés de part et d'autre de la trajectoire principale dans une représentation 2D de l'environnement simulé, vu de dessus.
Ainsi, un sentier est l'ensemble des solutions possibles au problème d'optimisation du placement des phares respectant le critère de distance défini ci-dessus.
Déterminer un sentier parallèle à la trajectoire principale nécessite quelques calculs géométriques, majoritairement situés dans la détermination des virages intérieurs de la courbe. Un module informatique tel que par exemple Shapely propose une fonction de commodité permettant de réaliser automatiquement ces calculs.
Les sentiers tels que définis ne tiennent pas compte de l'environnement.
Pour respecter les propriétés de visibilité et d'absence de collisions, on peut utiliser un algorithme de moulage par rayons, « Ray casting » en anglais. Cela consisterait en la construction d'un rayon partant de la trajectoire, à la normale de chacun des points de cette trajectoire.
La présente invention propose un nouvel algorithme permettant d'atteindre le même résultat en utilisant uniquement des opérations ensemblistes. Nous allons construire une médiatrice M pour chaque couple ti, t/’+l) de points consécutifs de la trajectoire principale. Les moitiés gauche Mg et droite Md de cette médiatrice jouerons le rôle de rayons. Les zones restreintes ainsi que les sentiers idéaux Sg (gauche) et Sd (droit) déterminés précédemment joueront quant à eux le rôle de limites sur lesquelles les rayons s'arrêteront.
Nous ne présenterons que la génération du sentier réel droit, la détermination du côté gauche étant en tous points similaire. L'idée générale de l'algorithme présenté ici est dans un premier temps de déterminer l'ensemble Id des intersections entre la demi-médiatrice droite et l'union de l'environnement (parois et poteaux) et du sentier idéal droit :
Id = {m £ Md Wz £ Z, m Cl (z U Sd) 0} Il s'agit ensuite de déterminer, le point p inclus dans Id le plus proche de l'origine de la demi-médiatrice Md.
La figure 5 illustre l'algorithme avec deux exemples sur une trajectoire sous-échantillonnée, permettant ainsi de dessiner les rayons construits sans saturer l'image. L'ensemble Id peut ne contenir qu'un seul point, la médiatrice ne traversant pas d'obstacles, auquel cas ce point sera utilisé pour construire le sentier adapté. C'est le cas le plus simple, visible pour la demi-médiatrice droite entre t38 et t39.
Cet ensemble peut également contenir un point et un ensemble de segments issus de l'intersection entre les zones restreintes et la demi- médiatrice. Il faudra alors sélectionner le point le plus proche de l'origine de la demi-médiatrice parmi l'ensemble des points inclus dans ces segments d'intersection. C'est le cas pour la demi-médiatrice droite des points t36 et t37.
La figure 6 illustre un résultat lorsque l'algorithme est appliqué sur une trajectoire principale correctement échantillonnée.
Les sentiers adaptés gauche 71 et droit 72 sur la figure 7 constituent donc l'ensemble de positions candidates pour le phare. Il s'agit ensuite de déterminer l'orientation du phare en chaque position candidate en construisant un champ de vision local. La présente invention prévoit une détermination analytique de l'orientation du phare. Pour ce faire, cette détermination est réalisée lors d'une phase d'évaluation au cours de laquelle chaque position candidate est évaluée.
Afin d'évaluer la pertinence d'un point , il faut déterminer une méthode de calcul de l'orientation a du phare, permettant de transformer ce point en une solution p, cf). Nous allons construire une fonction qui parcourt l'ensemble des points de la section de trajectoire.
Lorsque l'on considère un seul point de l'un des sentiers adaptés, l'ensemble des points de la trajectoire est compris dans un secteur circulaire virtuel, défini par deux rayons et une portée. Nous allons modéliser ces rayons par deux vecteurs Umin et Umax. L i dée globale est d'agrandir le secteur circulaire virtuel pour qu'il inclue chacun des points de Tk, et ce tant que le secteur virtuel n'a pas atteint les dimensions maximales de la zone de diffusion du phare.
La figure 8 présente différentes étapes de l'agrandissement du secteur circulaire virtuel. Les vecteurs Umin et Umax sont mis à jour au besoin, à chaque ajout de point tk, si le point est à l'extérieur du secteur circulaire. Si mise à jour il y a, on vérifie que l'angle d'ouverture 6 du secteur virtuel est toujours inférieur à l'angle maximal permis par le phare. La distance entre le point à ajouter et la position candidate du phare est également calculée. Si les deux conditions 6 < Qmax et ll - tdl < portée sont respectées, il est possible de couvrir tk depuis p.
Bien que les vérifications précédentes garantissent la présence du point tk dans le secteur de diffusion du phare positionné en p, les occlusions potentielles dues à l'environnement ne garantissent pas la visibilité de l'ensemble des points de la trajectoire à suivre depuis la position candidate. En effet, un obstacle pourrait occulter la ligne de vue, rendant la solution inefficace en pratique. Le modèle de l'environnement comprend un ensemble O de polygones représentant les obstacles (parois, poteaux, ...).
Nous allons construire un test de visibilité. Afin d'accepter un nouveau point tk dans la section couverte, il faut non seulement que ce point soit visible depuis p, mais également que le segment allant de tk-i à tk soit intégralement visible pour que l'on puisse se rendre de l'un à l'autre sans perdre le lien visuel avec le phare. Pour garantir cette visibilité, il faut qu'aucun obstacle ne se trouve dans le triangle A défini par les points tk-i, tk et p. Nous pouvons pour cela utiliser l'opérateur d'intersection et ainsi vérifier la propriété de visibilité : vo e o,o n A= 0
L'évaluation à proprement parler consiste à calculer un score pour chaque champ de vision local déterminé. Le score est proportionnel au segment pris dans le champ de vision local. Nous pouvons calculer directement cette distance en sommant au fur et à mesure les distances lltk-i - t/dl, ou simplement en comptant le nombre de points couverts, ce qui est moins coûteux et aussi discriminant pour le choix de la solution optimale.
Pour la première solution, soit / l'indice du premier point ti non couvert depuis la position p, le score est donné par la somme suivante :
Figure imgf000016_0001
La phase d'évaluation permet donc pour chaque position candidate de construire un champ de vision local et de lui associer un score.
On va maintenant décrire la construction d'une solution globale.
La construction d'une solution globale optimale consiste à résoudre le problème local de maximisation de trajectoire couverte en commençant par le début de la trajectoire. On retient la position candidate dont le champ de vision local intègre le premier point de la trajectoire principale et présente le score le plus élevé (parmi tous les champs de vision intégrant le premier point de la trajectoire principale). Il faut ensuite réduire la trajectoire à traiter en soustrayant la partie couverte précédemment. On boucle ainsi tant qu'il reste des points dans la trajectoire à traiter.
La figure 9 permet de visualiser les différentes étapes nécessaires au suivi de la trajectoire principale de bout en bout. Les points évalués localement ainsi que leurs scores associés sont dessinés sur chaque étape. La solution optimale est choisie parmi ces points permettant par la même occasion de déterminer la section couverte. Cette solution est représentée par le secteur circulaire de diffusion sur la figure 9. Ce processus est ensuite répété jusqu'au bout de la trajectoire.
Sur la figure 9, à l'étape 0, on distingue le champ de vision local 91 dont la source est située contre une paroi de l'environnement sur un sentier adapté. La source du champ de vision coïncide avec une position candidate 92 ayant eu le score le plus élevé parmi un ensemble de positions candidates dans la portée du point de départ 93. La position candidate 92 qui a été sélectionnée se trouve sur le sentier gauche. L'angle d'ouverture de ce champ de vision local est inférieur ou égal au champ de vision maximum du phare. Le segment ou la section couverte par le champ de vision est la plus grande possible.
A l'étape 1, on considère le reste de la trajectoire principale. Le point de départ est désormais le premier point du reste de la trajectoire non couverte par le premier segment. De la même manière, on considère la position ayant obtenu le meilleur score. Le champ de vision local de cette position permet de déterminer le segment couvert. L'algorithme est appliqué successivement sur le reste de la trajectoire jusqu'à atteindre le point d'arrivée, 94 à l'étape 4 sur la figure 9. La solution globale ainsi obtenue est résumée sur la figure 10, où les étapes successives sont superposées sur la carte, formant une solution optimale. La pertinence de cette solution s'évalue par le nombre d'étapes nécessaires à la réalisation de la mission.
La présente invention propose ainsi des solutions pour lesquelles les positions candidates sont sur les sentiers adaptés. Cela est optimal pour une trajectoire purement rectiligne. Cependant, dans de nombreux cas pratiques, la trajectoire à suivre est loin d'être rectiligne. Pour ce faire, la présente invention prévoit d'étendre l'espace de solutions à toute la surface entre les sentiers gauche et droit de façon à mieux couvrir les sections à forte courbure. Augmenter ainsi l'espace de solutions a évidemment un coût en calculs, mais peut permettre d'obtenir de meilleures solutions par rapport à des positions sur les sentiers.
Afin de déterminer la surface de solutions Pk, on détermine d'abord une surface Sk comme étant la surface de la zone de détection optimisée. Par ailleurs, le phare ne devant pas gêner le mobile dans le suivi de sa trajectoire principale, nous écartons les points trop proches de cette dernière. Notons Rk cette zone réservée, qui est définie par la contrainte de respect de la distance de sécurité ds de la manière suivante :
Rk = {q £ R2 V Vt £ Tk, || t — || < ds}
La figure 11 présente les surfaces et zones réservées 110 et 111 de deux sections distinctes de la trajectoire principale. Ainsi l'ensemble Pk des solutions pour une section k sera défini par la différence entre ces deux surfaces :
Pk = Sk - Rk
La surface Pk est un espace de solutions plus large que les précédents sentiers et offre probablement de meilleures solutions locales.
On prévoit également d'évaluer les solutions de Pk en calculant des scores. Or, la fonction d proposée ci-dessus ne permet de fournir un score que pour un point donné. Il nous faut donc échantillonner la surface Pk, nous allons pour cela utiliser une grille uniformément espacée, générant ainsi un sous- ensemble de points Ek c Pk. Ayant maintenant affaire à des points, il est possible d'évaluer leur pertinence respective. La figure 12 présente la grille de points évalués, ainsi que leur score. Une fois de plus, la discrétisation, ici la distance entre chaque échantillon testé, est volontairement choisie pour simplifier la compréhension et la visualisation des résultats. Il est toutefois possible de faire varier cette distance afin de tester plus de candidats, et ainsi ajuster le rapport coût/performance de l'algorithme d'optimisation locale.
La solution locale trouvée est meilleure, car le point choisi couvre une portion plus longue de la trajectoire principale. En contrepartie, le coût total de l'optimisation augmente linéairement avec le nombre de points testés.
Afin de diminuer le coût, une stratégie d'évaluation multi-échelle permettant de réduire drastiquement le nombre de points à évaluer a été mise en place. En effet, il est possible d'obtenir une résolution fine, sans tester l'ensemble de la grille à haute résolution. L'astuce consiste à faire un premier échantillonnage à faible résolution, procéder à l'évaluation des points, sélectionner le meilleur, puis répéter le processus avec une résolution plus fine, mais dans une zone limitée autour du meilleur point précédemment sélectionné.
Ainsi, pour obtenir une résolution de 1cm = 0.01m, dans une portée de 5m avec une seule échelle, il faudrait :
Card E) < (^) 2 ~ 105
En Appliquant cette fois-ci une recherche avec une succession d'échelles (par exemple d = 1, 0.1, 0.01) le nombre d'échantillons à tester est déterminable de la manière suivante : 10
Figure imgf000019_0001
2
Cette approche permet donc de limiter très fortement le nombre de calculs nécessaires pour obtenir une résolution fine. Toutefois, ne testant pas l'ensemble des points de la grille à résolution fine, il est possible de tomber dans un extremum local, dont la valeur peut être très éloignée de l'optimum global qui aurait été trouvé avec l'approche mono-résolution. Il est alors possible de sélectionner plus d'un point à chaque étape, limitant ainsi ce risque. Bien que ce garde-fou ait un coût en calculs, il reste très limité par rapport au coût de l'approche mono-résolution :
Figure imgf000020_0001
La figure 13 présente l'approche multi-échelle et les résultats obtenus à chaque résolution, ainsi que le résultat obtenu avec l'approche mono-résolution avec d = 0.1. Une rapide analyse quantitative et qualitative permet de valider l'approche, qui permet d'obtenir des résultats aussi précis. Il est même possible, au vu de la réduction du coût en calcul, de calculer à une résolution supérieure, ce qui prendrait trop de temps en pratique pour l'approche monoéchelle.
La succession d'optimisations locales obtenues avec l'approche par surface est présentée sur la figure 14. Bien que la discrétisation choisie soit volontairement grossière afin de faciliter la visualisation, on peut constater une amélioration des positions choisies, particulièrement autour des virages important de la courbe principale.
Bien entendu, l'invention n'est pas limitée aux exemples qui viennent d'être décrits. De nombreuses modifications peuvent être apportées à ces exemples sans sortir du cadre de la présente invention telle que décrite

Claims

REVENDICATIONS
1. Procédé pour déterminer des positions optimisées d'au moins un objet doté d'un champ de vision pour le suivi d'une trajectoire dans un environnement simulé comprenant des obstacles, le champ de vision comprenant une source, une portée et un angle d'ouverture, caractérisé en ce que le procédé est mis en œuvre par un ordinateur et comprend les étapes suivantes : a) sélection d'un ensemble de positions candidates, b) pour chaque position candidate, construction d'un champ de vision local placé à cette position candidate et orienté suivant les étapes suivantes : bl) définition de deux vecteurs positionnés à la position candidate et orientés vers un premier point d'un segment de la trajectoire principale, ce premier point étant à la portée de l'objet lorsque l'objet est placé à la position candidate, b2) balayage point par point du segment ; à chaque nouveau point balayé du segment, les vecteurs pointent vers deux points balayés les plus écartés vis-à-vis de la position candidate, b3) fin de balayage lorsqu'un nouveau point balayé est considéré non valide ; un point balayé étant considéré non valide lorsque ce point balayé se trouve hors de portée ou l'angle formé par les deux vecteurs est supérieur à l'angle d'ouverture du champ de vision ou un obstacle se trouve dans le triangle formé par la position candidate, le précédent point balayé et le nouveau point balayé ; le champ de vision local étant défini par la portée du champ de vision et un angle d'ouverture formé par les deux vecteurs pour le dernier point balayé valide, c) affectation d'un score à chaque position candidate, d) construction globale des positions optimisées en réalisant les étapes suivantes : dl) à partir d'une extrémité de la trajectoire principale, détermination d'une position candidate ayant le score le plus élevé parmi un ensemble de positions candidates ayant un champ de vision local couvrant ledit point de départ ; le champ de vision local de la position candidate ainsi déterminée couvrant un segment de la trajectoire principale, d2) application successive de l'étape précédente sur le reste de la trajectoire principale jusqu'à ce qu'un champ de vision local couvre une autre extrémité de la trajectoire principale, d3) sauvegarde de l'ensemble des positions candidates ainsi déterminées comme étant les positions optimisées pour le placement dudit objet.
2. Procédé selon la revendication 1, caractérisé en ce que l'étape a) de sélection d'un ensemble de positions candidates comprend les étapes suivantes :
- détermination d'une zone de détection optimisée le long de la trajectoire principale, cette zone étant délimitée par une trajectoire virtuelle gauche, dite sentier gauche, et une trajectoire virtuelle droite, dite sentier droit, les deux trajectoires virtuelles étant à une distance fixe de la trajectoire principale,
- pour tout point de la trajectoire principale, détermination d'une position candidate disposée perpendiculairement à la trajectoire principale et située sur le sentier gauche ou à une distance minimale de sécurité d'un obstacle si cet obstacle se trouve entre le sentier gauche et le point de la trajectoire principale,
- pour tout point de la trajectoire principale, détermination d'une position candidate disposée perpendiculairement à la trajectoire principale et située sur le sentier droit ou à une distance minimale de sécurité d'un obstacle si cet obstacle se trouve entre le sentier droit et le point de la trajectoire principale.
3. Procédé selon la revendication 2, caractérisé en ce que la distance entre la trajectoire principale et le sentier gauche ou le sentier droit est déterminée en réalisant les étapes suivantes :
- détermination d'une corde C du champ de vision comme étant la distance maximum d'une corde inscrite dans le champ de vision,
- détermination d'une bande de tolérance comprenant la corde C, la distance entre la trajectoire principale et le sentier gauche ou droit est définie comme étant égale à une hauteur entre la source et le milieu de la bande de tolérance.
4. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape a) de sélection d'un ensemble de positions candidates comprend en outre les étapes suivantes :
- détermination d'une zone réservée autour de la trajectoire principale, cette zone réservée étant moins large que la zone de détection optimisée ; des espaces obtenus entre la zone de détection optimisée et la zone réservée constituant des zones différentielles, et
- sélection de tout ou partie des points des zones différentielles comme des positions candidates.
5. Procédé selon la revendication 4, caractérisé en ce que la sélection d'une partie des points des zones différentielles est obtenue lors de chaque étape dl) de détermination d'une position candidate ayant le score le plus élevé ; ledit ensemble de positions candidates comprenant en outre des positions candidates obtenues selon les étapes suivantes : dll) identification de parties des zones différentielles se trouvant à portée de la dite extrémité de la trajectoire principale ; pour chaque partie identifiée, réalisation des étapes suivantes : d 12) échantillonnage à une résolution, dl3) évaluation en calculant un score pour chaque point obtenu après échantillonnage, dl4) sélection du meilleur point, dl5) détermination d'une zone limitée autour du meilleur point sélectionné, dl6) répétition des étapes dl2) à dl5) avec augmentation de ladite résolution à chaque répétition jusqu'à atteindre un niveau de résolution prédéterminé, puis sélection du dernier meilleur point comme position candidate.
6. Procédé selon la revendication 4, caractérisé en ce que la sélection d'une partie des points dans une zone différentielle comprend les étapes suivantes : d 12) échantillonnage à une résolution, dl3) évaluation en calculant un score pour chaque point obtenu après échantillonnage, dl4) sélection du meilleur point, d 15) détermination d'une zone limitée autour du meilleur point sélectionné, dl6) répétition des étapes d 12) à dl5) avec augmentation de ladite résolution à chaque répétition jusqu'à atteindre un niveau de résolution prédéterminé, puis sélection du dernier meilleur point comme position candidate. 22 -
7. Procédé selon la revendication 6, caractérisé en ce que chaque zone différentielle est découpée en plusieurs sous-zones différentielles comprenant plusieurs points échantillonnés, et en ce que les étapes dl2) à dl5) sont réalisées sur chacune des sous-zones différentielles ainsi découpées.
8. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les points de la trajectoire principale sont déterminés par échantillonnage aléatoire, systématique ou selon une règle prédéterminée.
9. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le score est une longueur du segment balayé ou le nombre de points balayés.
10. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'objet est un dispositif électronique de détection.
11. Système de traitement de données comprenant des moyens pour mettre en œuvre les étapes du procédé selon l'une quelconque des revendications 1 à 10.
12. Produit programme d'ordinateur comprenant des instructions qui, lorsque le programme est exécuté par un ordinateur, conduisent celui-ci à mettre en œuvre les étapes du procédé selon l'une quelconque des revendications 1 à 10.
PCT/EP2022/079206 2021-11-10 2022-10-20 Procédé pour déterminer des positions optimisées d'un objet pour le suivi d'une trajectoire dans un environnement simulé. Ceased WO2023083577A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FRFR2111970 2021-11-10
FR2111970A FR3129003B1 (fr) 2021-11-10 2021-11-10 Procédé pour déterminer des positions optimisées d’un objet pour le suivi d’une trajectoire dans un environnement simulé.

Publications (1)

Publication Number Publication Date
WO2023083577A1 true WO2023083577A1 (fr) 2023-05-19

Family

ID=80735953

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2022/079206 Ceased WO2023083577A1 (fr) 2021-11-10 2022-10-20 Procédé pour déterminer des positions optimisées d'un objet pour le suivi d'une trajectoire dans un environnement simulé.

Country Status (2)

Country Link
FR (1) FR3129003B1 (fr)
WO (1) WO2023083577A1 (fr)

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20150348235A1 (en) * 2014-06-03 2015-12-03 Mitsubishi Electric Research Laboratories, Inc. Distributed path planning for mobile sensors
US20170205490A1 (en) * 2014-07-21 2017-07-20 Sikorsky Aircraft Corporation Coverage optimization for sensor networks
EP3846067A1 (fr) * 2019-12-31 2021-07-07 Data Smart Process Procédé et système de déploiement de caméras de surveillance

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20150348235A1 (en) * 2014-06-03 2015-12-03 Mitsubishi Electric Research Laboratories, Inc. Distributed path planning for mobile sensors
US20170205490A1 (en) * 2014-07-21 2017-07-20 Sikorsky Aircraft Corporation Coverage optimization for sensor networks
EP3846067A1 (fr) * 2019-12-31 2021-07-07 Data Smart Process Procédé et système de déploiement de caméras de surveillance

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
DUAN JUN ET AL: "VisualVital: An observation model for multiple sections of scenes", 2017 IEEE SMARTWORLD, UBIQUITOUS INTELLIGENCE & COMPUTING, ADVANCED & TRUSTED COMPUTED, SCALABLE COMPUTING & COMMUNICATIONS, CLOUD & BIG DATA COMPUTING, INTERNET OF PEOPLE AND SMART CITY INNOVATION (SMARTWORLD/SCALCOM/UIC/ATC/CBDCOM/IOP/SCI), IEEE, 4 August 2017 (2017-08-04), pages 1 - 8, XP033365961, DOI: 10.1109/UIC-ATC.2017.8397546 *

Also Published As

Publication number Publication date
FR3129003B1 (fr) 2023-10-13
FR3129003A1 (fr) 2023-05-12

Similar Documents

Publication Publication Date Title
Wolcott et al. Robust LIDAR localization using multiresolution Gaussian mixture maps for autonomous driving
EP2356493B1 (fr) Procede de modelisation geologique de donnees sismiques par correlation de traces
EP2724203B1 (fr) Génération de données de carte
EP2937812B1 (fr) Système de localisation d&#39;un même véhicule dans plusieurs zones différentes les unes des autres dans lesquelles ledit véhicule passe consécutivement
WO2013175022A1 (fr) Systèmes et procédés de topographie et de reconstruction tridimensionnelle à partir d&#39;un nuage de points et supports de stockage informatique pour ces systèmes et procédés
FR3052275A1 (fr) Procede et systeme de determination de cellules traversees par un axe de mesure ou de visualisation
EP3679517B1 (fr) Procede de determination des bords saillants d&#39;une cible sur une image
CN104050473B (zh) 一种基于矩形邻域分析的道路数据提取方法
FR2964765A1 (fr) Procede de recherche de plus court chemin avec heuristique
EP3832338B1 (fr) Procede de geolocalisation et de qualification de dispositifs d&#39;infrastructure de signalisation
EP3311604B1 (fr) Système d&#39;optimisation du déploiement de capteurs pour la localisation de cibles, utilisation du système et procédé d&#39;optimisation
EP4256274A1 (fr) Procédé et dispositif de génération de trajectoire d&#39;un appareil mobile respectant une contrainte temporelle prédéterminée
WO2023083577A1 (fr) Procédé pour déterminer des positions optimisées d&#39;un objet pour le suivi d&#39;une trajectoire dans un environnement simulé.
Zhan et al. Towards visibility estimation and noise-distribution-based defogging for LiDAR in autonomous driving
Espindola et al. Development of an autonomous measurement system for estimation of snow profile on road surfaces
FR3123862A1 (fr) Procédé et dispositif de contrôle d’un véhicule autonome
FR3076795A1 (fr) Procede d&#39;assistance au stationnement pour un vehicule a moteur
FR2978276A1 (fr) Procede de modelisation de batiments a partir d&#39;une image georeferencee
FR2991091A1 (fr) Systeme et procede de reconstruction tridimensionnelle et support de stockage informatique pour ces systeme et procede
EP1115010A9 (fr) Procédé pour déterminer les distances de visibilité d&#39;une voie de circulation
EP4121718B1 (fr) Procédé de calcul d&#39;un chemin, produit programme d&#39;ordinateur, support d&#39;informations et dispositif associés
EP3903282B1 (fr) Méthode de segmentation d&#39;une image
WO2006003268A1 (fr) Precede general de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles d’altitudes variables.
WO2006003267A1 (fr) Procede de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles
WO2023061915A1 (fr) Procédé de détection d&#39;une limite d&#39;une voie de circulation

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: 22802642

Country of ref document: EP

Kind code of ref document: A1

122 Ep: pct application non-entry in european phase

Ref document number: 22802642

Country of ref document: EP

Kind code of ref document: A1