]> rtime.felk.cvut.cz Git - hubacji1/iamcar.git/blob - decision_control/slotplanner.cc
Set slot heading with `satAll()`
[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 void ParallelSlot::fipr(RRTNode *n)
233 {
234         return this->fipr(new BicycleCar(n->x(), n->y(), n->h()));
235 }
236
237 void ParallelSlot::fipr(BicycleCar *B)
238 {
239         std::vector<RRTNode *> cusp;
240         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
241         int di = 1;
242         if (this->slotSide() == LEFT)
243                 di = -1;
244         if (this->slotType() == PERPENDICULAR) {
245                 this->DH(di * 0.01 / B->out_radi()); // TODO car in slot h()
246                 RRTNode *cc;
247                 if (this->slotSide() == LEFT)
248                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
249                 else
250                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
251                 BicycleCar *p;
252                 int i = 1;
253                 p = B->move(cc, i * this->DH());
254                 while (
255                         !this->slot().collide(p->frame())
256                         && this->slot().collide(p)
257                 ) {
258                         delete p;
259                         i += 10;
260                         p = B->move(cc, i * this->DH());
261                 }
262                 i -= 10;
263                 p = B->move(cc, i * this->DH());
264                 while (
265                         !this->slot().collide(p->frame())
266                         && this->slot().collide(p)
267                 ) {
268                         delete p;
269                         i += 1;
270                         p = B->move(cc, i * this->DH());
271                 }
272                 i -= 1;
273                 p = B->move(cc, i * this->DH());
274                 cusp.push_back(new RRTNode(p->x(), p->y(), p->h()));
275                 std::reverse(cusp.begin(), cusp.end());
276                 this->cusp().push_back(cusp);
277                 return;
278         }
279         this->DH(di * 0.01 / B->out_radi());
280         BicycleCar *c;
281         c = this->flncr(B);
282         c->s(B->s() + 1);
283         while ((
284                 this->slotSide() == LEFT
285                 && this->slot().collide(new RRTNode(c->lfx(), c->lfy(), 0))
286         ) || (
287                 this->slotSide() == RIGHT
288                 && this->slot().collide(new RRTNode(c->rfx(), c->rfy(), 0))
289         )) {
290                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
291                 BicycleCar *cc = this->flncr(c);
292                 cc->s(c->s() + 1);
293                 delete c;
294                 c = cc;
295         }
296         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
297         std::reverse(cusp.begin(), cusp.end());
298         this->cusp().push_back(cusp);
299 }
300
301 BicycleCar *ParallelSlot::flnc(
302         BicycleCar *B,
303         std::vector<CircleObstacle>& co,
304         std::vector<SegmentObstacle>& so
305 )
306 {
307         RRTNode *cc;
308         if (this->slotSide() == LEFT) {
309                 if (int(B->s()) % 2 == 0)
310                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
311                 else
312                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
313         } else {
314                 if (int(B->s()) % 2 == 0)
315                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
316                 else
317                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
318         }
319         BicycleCar *p;
320         int i = 1;
321         p = B->move(cc, i * this->DH());
322         while (
323                 !this->slot().collide(p->frame())
324                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
325         ) {
326                 delete p;
327                 i += 10;
328                 p = B->move(cc, i * this->DH());
329                 bool end = false;
330                 std::vector<RRTEdge *> eds = p->frame();
331                 for (auto o: co)
332                         if (o.collide(eds))
333                                 end = true;
334                 for (auto o: so)
335                         if (o.collide(eds))
336                                 end = true;
337                 for (auto e: eds)
338                         delete e;
339                 if (end)
340                         break;
341         }
342         i -= 10;
343         p = B->move(cc, i * this->DH());
344         while (
345                 !this->slot().collide(p->frame())
346                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
347         ) {
348                 if (this->isInside(p)) {
349                         i += 1;
350                         break;
351                 }
352                 delete p;
353                 i += 1;
354                 p = B->move(cc, i * this->DH());
355                 bool end = false;
356                 std::vector<RRTEdge *> eds = p->frame();
357                 for (auto o: co)
358                         if (o.collide(eds))
359                                 end = true;
360                 for (auto o: so)
361                         if (o.collide(eds))
362                                 end = true;
363                 for (auto e: eds)
364                         delete e;
365                 if (end)
366                         break;
367         }
368         delete p;
369         return B->move(cc, (i - 1) * this->DH());
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 }