]> rtime.felk.cvut.cz Git - hubacji1/iamcar.git/blob - decision_control/slotplanner.cc
Just reorder methods
[hubacji1/iamcar.git] / decision_control / slotplanner.cc
1 /*
2 This file is part of I am car.
3
4 I am car is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 I am car is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with I am car. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include <algorithm>
19 #include <cmath>
20 #include <list>
21 #include <queue>
22 #include "slotplanner.h"
23
24 ParallelSlot::ParallelSlot()
25 {}
26
27 // getter
28 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
29 {
30         return this->cusp_;
31 }
32
33 float ParallelSlot::DH() const
34 {
35         return this->DH_;
36 }
37
38 PolygonObstacle &ParallelSlot::slot()
39 {
40         return this->slot_;
41 }
42
43 float ParallelSlot::slotHeading()
44 {
45         return this->slotHeading_;
46 }
47
48 SlotSide ParallelSlot::slotSide()
49 {
50         return this->slotSide_;
51 }
52
53 SlotType ParallelSlot::slotType()
54 {
55         return this->slotType_;
56 }
57
58 // setter
59 void ParallelSlot::DH(float dh)
60 {
61         this->DH_ = dh;
62 }
63
64 void ParallelSlot::setAll()
65 {
66         // slot heading
67         float y0 = this->slot().bnodes()[0]->y();
68         float x0 = this->slot().bnodes()[0]->x();
69         float y3 = this->slot().bnodes()[3]->y();
70         float x3 = this->slot().bnodes()[3]->x();
71         float dy = y0 - y3;
72         float dx = x0 - x3;
73         this->slotHeading_ = atan2(dy, dx);
74         // slot side
75         float y1 = this->slot().bnodes()[1]->y();
76         float x1 = this->slot().bnodes()[1]->x();
77         if (sgn((x1 - x3) * (y0 - y3) - (y1 - y3) * (x0 - x3)) < 0)
78                 this->slotSide_ = LEFT;
79         else
80                 this->slotSide_ = RIGHT;
81         // slot type
82         float d1 = EDIST(
83                 this->slot().bnodes()[0],
84                 this->slot().bnodes()[1]
85         );
86         float d2 = EDIST(
87                 this->slot().bnodes()[1],
88                 this->slot().bnodes()[2]
89         );
90         if (d1 > d2)
91                 this->slotType_ = PERPENDICULAR;
92         else
93                 this->slotType_ = PARALLEL;
94 }
95
96 // other
97 void ParallelSlot::fip(
98         std::vector<CircleObstacle>& co,
99         std::vector<SegmentObstacle>& so
100 )
101 {
102         if (this->slotType() == PERPENDICULAR) {
103                 // TODO different slot headings
104                 // this is jus for slot heading = pi / 2
105                 this->DH(0.01 / BCAR_TURNING_RADIUS);
106                 BicycleCar *perc = nullptr;
107                 RRTNode *cc = nullptr;
108                 BicycleCar *p = nullptr;
109                 int i = 0;
110                 float x;
111                 float h;
112                 float y;
113                 // parking backward
114                 x = this->slot().bnodes()[3]->x();
115                 y = this->slot().bnodes()[3]->y();
116                 h = 0;
117                 // -> top
118                 x -= BCAR_DIST_FRONT;
119                 y = this->slot().bnodes()[3]->y();
120                 y += BCAR_OUT_RRADI - BCAR_TURNING_RADIUS;
121                 if (perc)
122                         delete perc;
123                 perc = new BicycleCar(x, y, h);
124                 if (cc)
125                         delete cc;
126                 cc = perc->ccl();
127                 if (p)
128                         delete p;
129                 p = perc->move(cc, i * this->DH());
130                 while (p->x() < 0) {
131                         delete p;
132                         p = perc->move(cc, i * this->DH());
133                         i++;
134                 }
135                 // -> bottom
136                 // (reset for parking backward)
137                 x = this->slot().bnodes()[0]->x();
138                 y = this->slot().bnodes()[0]->y();
139                 h = 0;
140                 // -> bottom
141                 x -= BCAR_DIST_FRONT;
142                 // get y from quadratic equation
143                 float tmpD = pow(-2 * this->slot().bnodes()[0]->y(), 2);
144                 tmpD -= 4 * (
145                         pow(x - this->slot().bnodes()[0]->x(), 2) +
146                         pow(this->slot().bnodes()[0]->y(), 2) -
147                         pow(BCAR_IN_RADI, 2)
148                 );
149                 y = 2 * this->slot().bnodes()[0]->y();
150                 y += sqrt(tmpD);
151                 y /= 2;
152                 y -= BCAR_TURNING_RADIUS;
153                 // -- end of quadratic equation
154                 if (perc)
155                         delete perc;
156                 perc = new BicycleCar(x, y, h);
157                 if (cc)
158                         delete cc;
159                 cc = perc->ccl();
160                 if (p)
161                         delete p;
162                 p = perc->move(cc, i * this->DH());
163                 while (p->x() < 0) {
164                         delete p;
165                         p = perc->move(cc, i * this->DH());
166                         i++;
167                 }
168                 // store nodes
169                 std::vector<RRTNode *> cusp;
170                 cusp.push_back(new RRTNode(p->x(), p->y(), p->h()));
171                 cusp.push_back(new RRTNode(x, y, h));
172                 this->cusp().push_back(cusp);
173                 return;
174         }
175         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
176         // RRTNode.s() works as iteration level
177         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
178         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
179         int di = -1;
180         if (this->slotSide() == LEFT)
181                 di = 1;
182         BicycleCar *CC = this->getEPC();
183         BicycleCar *B = this->getEP();
184         this->DH(di * 0.01 / CC->out_radi());
185         BicycleCar *c;
186         int i = 0;
187         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
188         while (!this->slot().collide(c->frame())) {
189                 bool end = false;
190                 std::vector<RRTEdge *> eds = c->frame();
191                 for (auto o: co)
192                         if (o.collide(eds))
193                                 end = true;
194                 for (auto o: so)
195                         if (o.collide(eds))
196                                 end = true;
197                 for (auto e: eds)
198                         delete e;
199                 if (!end)
200                         q.push(c);
201                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
202                 i += 1;
203         }
204         delete c; // not in q and collide
205         while (!q.empty()) {
206                 c = q.front();
207                 q.pop();
208                 if (this->isInside(c)) {
209                         goto createcuspandfinish;
210                 } else if (c->s() < 9) {
211                         BicycleCar *cc = this->flnc(c, co, so);
212                         cc->s(c->s() + 1);
213                         cc->bcparent(c);
214                         q.push(cc);
215                 } else {
216                         delete c; // not in q and collide
217                 }
218         }
219         std::swap(q, empty);
220         return;
221 createcuspandfinish:
222         std::vector<RRTNode *> cusp;
223         while (c) {
224                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
225                 c = c->bcparent();
226         }
227         std::reverse(cusp.begin(), cusp.end());
228         this->cusp().push_back(cusp);
229         std::swap(q, empty);
230 }
231
232 BicycleCar *ParallelSlot::flnc(
233         BicycleCar *B,
234         std::vector<CircleObstacle>& co,
235         std::vector<SegmentObstacle>& so
236 )
237 {
238         RRTNode *cc;
239         if (this->slotSide() == LEFT) {
240                 if (int(B->s()) % 2 == 0)
241                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
242                 else
243                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
244         } else {
245                 if (int(B->s()) % 2 == 0)
246                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
247                 else
248                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
249         }
250         BicycleCar *p;
251         int i = 1;
252         p = B->move(cc, i * this->DH());
253         while (
254                 !this->slot().collide(p->frame())
255                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
256         ) {
257                 delete p;
258                 i += 10;
259                 p = B->move(cc, i * this->DH());
260                 bool end = false;
261                 std::vector<RRTEdge *> eds = p->frame();
262                 for (auto o: co)
263                         if (o.collide(eds))
264                                 end = true;
265                 for (auto o: so)
266                         if (o.collide(eds))
267                                 end = true;
268                 for (auto e: eds)
269                         delete e;
270                 if (end)
271                         break;
272         }
273         i -= 10;
274         p = B->move(cc, i * this->DH());
275         while (
276                 !this->slot().collide(p->frame())
277                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
278         ) {
279                 if (this->isInside(p)) {
280                         i += 1;
281                         break;
282                 }
283                 delete p;
284                 i += 1;
285                 p = B->move(cc, i * this->DH());
286                 bool end = false;
287                 std::vector<RRTEdge *> eds = p->frame();
288                 for (auto o: co)
289                         if (o.collide(eds))
290                                 end = true;
291                 for (auto o: so)
292                         if (o.collide(eds))
293                                 end = true;
294                 for (auto e: eds)
295                         delete e;
296                 if (end)
297                         break;
298         }
299         delete p;
300         return B->move(cc, (i - 1) * this->DH());
301 }
302
303 void ParallelSlot::fipr(RRTNode *n)
304 {
305         return this->fipr(new BicycleCar(n->x(), n->y(), n->h()));
306 }
307
308 void ParallelSlot::fipr(BicycleCar *B)
309 {
310         std::vector<RRTNode *> cusp;
311         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
312         int di = 1;
313         if (this->slotSide() == LEFT)
314                 di = -1;
315         if (this->slotType() == PERPENDICULAR) {
316                 this->DH(di * 0.01 / B->out_radi()); // TODO car in slot h()
317                 RRTNode *cc;
318                 if (this->slotSide() == LEFT)
319                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
320                 else
321                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
322                 BicycleCar *p;
323                 int i = 1;
324                 p = B->move(cc, i * this->DH());
325                 while (
326                         !this->slot().collide(p->frame())
327                         && this->slot().collide(p)
328                 ) {
329                         delete p;
330                         i += 10;
331                         p = B->move(cc, i * this->DH());
332                 }
333                 i -= 10;
334                 p = B->move(cc, i * this->DH());
335                 while (
336                         !this->slot().collide(p->frame())
337                         && this->slot().collide(p)
338                 ) {
339                         delete p;
340                         i += 1;
341                         p = B->move(cc, i * this->DH());
342                 }
343                 i -= 1;
344                 p = B->move(cc, i * this->DH());
345                 cusp.push_back(new RRTNode(p->x(), p->y(), p->h()));
346                 std::reverse(cusp.begin(), cusp.end());
347                 this->cusp().push_back(cusp);
348                 return;
349         }
350         this->DH(di * 0.01 / B->out_radi());
351         BicycleCar *c;
352         c = this->flncr(B);
353         c->s(B->s() + 1);
354         while ((
355                 this->slotSide() == LEFT
356                 && this->slot().collide(new RRTNode(c->lfx(), c->lfy(), 0))
357         ) || (
358                 this->slotSide() == RIGHT
359                 && this->slot().collide(new RRTNode(c->rfx(), c->rfy(), 0))
360         )) {
361                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
362                 BicycleCar *cc = this->flncr(c);
363                 cc->s(c->s() + 1);
364                 delete c;
365                 c = cc;
366         }
367         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
368         std::reverse(cusp.begin(), cusp.end());
369         this->cusp().push_back(cusp);
370 }
371
372 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
373 {
374         RRTNode *cc;
375         if (this->slotSide() == LEFT) {
376                 if (int(B->s()) % 2 == 0)
377                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
378                 else
379                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
380         } else {
381                 if (int(B->s()) % 2 == 0)
382                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
383                 else
384                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
385         }
386         BicycleCar *p;
387         int i = 1;
388         p = B->move(cc, i * this->DH());
389         while (
390                 !this->slot().collide(p->frame())
391                 && ((
392                         this->slotSide() == LEFT
393                         && this->slot().collide(new RRTNode(
394                                 p->lfx(),
395                                 p->lfy(),
396                                 0
397                         ))
398                 ) || (
399                         this->slotSide() == RIGHT
400                         && this->slot().collide(new RRTNode(
401                                 p->rfx(),
402                                 p->rfy(),
403                                 0
404                         ))
405                 ))
406         ) {
407                 delete p;
408                 i += 10;
409                 p = B->move(cc, i * this->DH());
410         }
411         i -= 10;
412         p = B->move(cc, i * this->DH());
413         while (!this->slot().collide(p->frame())) {
414                 if(
415                         this->slotSide() == LEFT
416                         && !this->slot().collide(new RRTNode(
417                                 p->lfx(),
418                                 p->lfy(),
419                                 0
420                         ))
421                 ) {
422                         i += 1;
423                         break;
424                 }
425                 if(
426                         this->slotSide() == RIGHT
427                         && !this->slot().collide(new RRTNode(
428                                 p->rfx(),
429                                 p->rfy(),
430                                 0
431                         ))
432                 ) {
433                         i += 1;
434                         break;
435                 }
436                 i += 1;
437                 p = B->move(cc, i * this->DH());
438         }
439         delete p;
440         return B->move(cc, (i - 1) * this->DH());
441 }
442
443 RRTNode *ParallelSlot::fposecenter()
444 {
445         return this->slot().bnodes().front();
446 }
447
448 bool ParallelSlot::flast(
449         RRTNode *P,
450         bool right,
451         int il,
452         std::vector<RRTNode *> &cusp
453 )
454 {
455         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
456         RRTNode *cc;
457         if (right)
458                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
459         else
460                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
461         BicycleCar *p;
462         int i = 1;
463         p = B->move(cc, i * this->DH());
464         while (!this->slot().collide(p->frame())
465                         && (
466                                 (this->DH() > 0 && p->x() <= 0)
467                                 || (this->DH() < 0 && p->x() >= 0)
468                         )) {
469                 delete p;
470                 i += 10;
471                 p = B->move(cc, i * this->DH());
472         }
473         i -= 10;
474         p = B->move(cc, i * this->DH());
475         while (!this->slot().collide(p->frame())
476                         && (
477                                 (this->DH() > 0 && p->x() <= 0)
478                                 || (this->DH() < 0 && p->x() >= 0)
479                         )) {
480                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
481                         i += 1;
482                         break;
483                 }
484                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
485                         i += 1;
486                         break;
487                 }
488                 delete p;
489                 i += 1;
490                 p = B->move(cc, i * this->DH());
491         }
492         delete p;
493         p = B->move(cc, (i - 1) * this->DH());
494         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
495                 cusp.push_back(p);
496                 return true;
497         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
498                 cusp.push_back(p);
499                 return true;
500         } else if (il < 8) {
501                 cusp.push_back(p);
502                 return this->flast(p, !right, il + 1, cusp);
503         }
504         return false;
505 }
506
507 void ParallelSlot::fpose()
508 {
509         bool left = false; // right parking slot
510         float di = -1;
511         BicycleCar *CC = new BicycleCar(
512                 this->fposecenter()->x(),
513                 this->fposecenter()->y() - 0.01,
514                 this->slotHeading()
515         );
516         BicycleCar *B = new BicycleCar(
517                 CC->x() - CC->width() / 2,
518                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
519                 this->slotHeading()
520         );
521         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
522                 left = true;
523                 di = 1;
524                 delete B;
525                 B = new BicycleCar(
526                         CC->x() + CC->width() / 2,
527                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
528                         this->slotHeading()
529                 );
530         }
531         this->DH(di * 0.01 / CC->out_radi());
532         BicycleCar *p;
533         int i = 0;
534         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
535         while (!this->slot().collide(p->frame())) {
536                 std::vector<RRTNode *> tmpcusp;
537                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
538                 if (this->flast(p, left, 0, tmpcusp)) {
539                         this->cusp().push_back(tmpcusp);
540                         return;
541                 }
542                 i += 1;
543                 delete p;
544                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
545         }
546 }
547
548 BicycleCar *ParallelSlot::getEP()
549 {
550         // new pose for parallel parking to right slot
551         float tnx;
552         float tny;
553         float nx;
554         float ny;
555         BicycleCar *CC = this->getEPC();
556         // move left by car width / 2
557         tnx = CC->x() + CC->width() / 2 * cos(CC->h() + M_PI / 2);
558         tny = CC->y() + CC->width() / 2 * sin(CC->h() + M_PI / 2);
559         if (this->slotSide() == LEFT) {
560                 // move right by car width / 2
561                 tnx = CC->x() + CC->width() / 2 * cos(CC->h() - M_PI / 2);
562                 tny = CC->y() + CC->width() / 2 * sin(CC->h() - M_PI / 2);
563         }
564         if (this->slotType() == PARALLEL) {
565                 // move down
566                 nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
567                 ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
568         } else {
569                 // move down
570                 nx = tnx + (CC->length() - CC->wheelbase()) / 2 * cos(CC->h());
571                 ny = tny + (CC->length() - CC->wheelbase()) / 2 * sin(CC->h());
572         }
573         return new BicycleCar(nx, ny, CC->h());
574 }
575
576 BicycleCar *ParallelSlot::getEPC()
577 {
578         // new pose for parallel parking to right slot
579         float ta;
580         float nx;
581         float ny;
582         ta = this->slotHeading() + M_PI;
583         if (this->slotSide() == RIGHT)
584                 ta -= M_PI / 4;
585         else
586                 ta += M_PI / 4;
587         nx = this->fposecenter()->x() + 0.01 * cos(ta);
588         ny = this->fposecenter()->y() + 0.01 * sin(ta);
589         return new BicycleCar(nx, ny, this->slotHeading());
590 }
591
592 BicycleCar *ParallelSlot::getFP()
593 {
594         float x = this->slot().bnodes()[3]->x();
595         float y = this->slot().bnodes()[3]->y();
596         float h = this->slotHeading();
597         float nx;
598         float ny;
599         if (this->slotType() == PARALLEL) {
600                 if (this->slotSide() == LEFT) {
601                         nx = x + BCAR_WIDTH / 2 * cos(h + M_PI / 2);
602                         ny = y + BCAR_WIDTH / 2 * sin(h + M_PI / 2);
603                 } else {
604                         nx = x + BCAR_WIDTH / 2 * cos(h - M_PI / 2);
605                         ny = y + BCAR_WIDTH / 2 * sin(h - M_PI / 2);
606                 }
607                 x = nx + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * cos(h);
608                 y = ny + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * sin(h);
609         } else {
610                 if (this->slotSide() == LEFT) {
611                         h -= M_PI / 2;
612                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
613                                 * cos(h + M_PI);
614                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
615                                 * sin(h + M_PI);
616                         x = nx + (BCAR_DIAG_RRADI) * cos(h + M_PI / 2);
617                         y = ny + (BCAR_DIAG_RRADI) * sin(h + M_PI / 2);
618                 } else {
619                         h += M_PI / 2;
620                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
621                                 * cos(h - M_PI);
622                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
623                                 * sin(h - M_PI);
624                         x = nx + (BCAR_DIAG_RRADI) * cos(h - M_PI / 2);
625                         y = ny + (BCAR_DIAG_RRADI) * sin(h - M_PI / 2);
626                 }
627         }
628         return new BicycleCar(x, y, h);
629 }
630
631 bool ParallelSlot::isInside(BicycleCar *c)
632 {
633         bool inside = true;
634         RRTNode *tmpn;
635         tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
636         if (!this->slot().collide(tmpn))
637                 inside = false;
638         delete tmpn;
639         tmpn = new RRTNode(c->lrx(), c->lry(), 0);
640         if (!this->slot().collide(tmpn))
641                 inside = false;
642         delete tmpn;
643         tmpn = new RRTNode(c->rrx(), c->rry(), 0);
644         if (!this->slot().collide(tmpn))
645                 inside = false;
646         delete tmpn;
647         tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
648         if (!this->slot().collide(tmpn))
649                 inside = false;
650         delete tmpn;
651         return inside;
652 }
653
654 struct SamplingInfo ParallelSlot::getSamplingInfo()
655 {
656         struct SamplingInfo si;
657         if (this->slotType() == PARALLEL) {
658                 si.x = this->slot().bnodes().front()->x();
659                 si.y = this->slot().bnodes().front()->y();
660                 si.mr = BCAR_WIDTH / 2;
661                 si.mmh = 0;
662         } else {
663                 si.x = this->slot().bnodes().back()->x();
664                 si.x -= this->slot().bnodes().front()->x();
665                 si.x /= 2;
666                 si.x += this->slot().bnodes().front()->x();
667                 si.y = this->slot().bnodes().back()->y();
668                 si.y -= this->slot().bnodes().front()->y();
669                 si.y /= 2;
670                 si.y += this->slot().bnodes().front()->y();
671                 si.mr = 0;
672                 si.mmh = (M_PI - M_PI / 6) / 2;
673         }
674         si.r = BCAR_LENGTH;
675         si.h = M_PI;
676         si.mh = M_PI / 2;
677         si.sh = this->slotHeading();
678         if (this->slotSide() == RIGHT)
679                 si.dh = 1;
680         else
681                 si.dh = -1;
682         return si;
683 }