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         float y0 = this->slot().bnodes()[0]->y();
  46         float x0 = this->slot().bnodes()[0]->x();
  47         float y3 = this->slot().bnodes()[3]->y();
  48         float x3 = this->slot().bnodes()[3]->x();
  49         float dy = y0 - y3;
  50         float dx = x0 - x3;
  51         return atan2(dy, dx);
  52 }
  53
  54 SlotSide ParallelSlot::slotSide()
  55 {
  56         return this->slotSide_;
  57 }
  58
  59 SlotType ParallelSlot::slotType()
  60 {
  61         return this->slotType_;
  62 }
  63
  64 // setter
  65 void ParallelSlot::DH(float dh)
  66 {
  67         this->DH_ = dh;
  68 }
  69
  70 void ParallelSlot::setAll()
  71 {
  72         // slot side
  73         float y0 = this->slot().bnodes()[0]->y();
  74         float x0 = this->slot().bnodes()[0]->x();
  75         float y1 = this->slot().bnodes()[1]->y();
  76         float x1 = this->slot().bnodes()[1]->x();
  77         float y3 = this->slot().bnodes()[3]->y();
  78         float x3 = this->slot().bnodes()[3]->x();
  79         if (sgn((x1 - x3) * (y0 - y3) - (y1 - y3) * (x0 - x3)) < 0)
  80                 this->slotSide_ = LEFT;
  81         else
  82                 this->slotSide_ = RIGHT;
  83         // slot type
  84         float d1 = EDIST(
  85                 this->slot().bnodes()[0],
  86                 this->slot().bnodes()[1]
  87         );
  88         float d2 = EDIST(
  89                 this->slot().bnodes()[1],
  90                 this->slot().bnodes()[2]
  91         );
  92         if (d1 > d2)
  93                 this->slotType_ = PERPENDICULAR;
  94         else
  95                 this->slotType_ = PARALLEL;
  96 }
  97
  98 // other
  99 void ParallelSlot::fip()
 100 {
 101         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
 102         // RRTNode.s() works as iteration level
 103         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
 104         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
 105         int di = -1;
 106         if (this->slotSide() == LEFT)
 107                 di = 1;
 108         BicycleCar *CC = this->getEPC();
 109         BicycleCar *B = this->getEP();
 110         this->DH(di * 0.01 / CC->out_radi());
 111         BicycleCar *c;
 112         int i = 0;
 113         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 114         while (!this->slot().collide(c->frame())) {
 115                 q.push(c);
 116                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 117                 i += 1;
 118         }
 119         delete c; // not in q and collide
 120         while (!q.empty()) {
 121                 c = q.front();
 122                 q.pop();
 123                 if (this->isInside(c)) {
 124                         goto createcuspandfinish;
 125                 } else if (c->s() < 9) {
 126                         BicycleCar *cc = this->flnc(c);
 127                         cc->s(c->s() + 1);
 128                         cc->bcparent(c);
 129                         q.push(cc);
 130                 } else {
 131                         delete c; // not in q and collide
 132                 }
 133         }
 134         std::swap(q, empty);
 135         return;
 136 createcuspandfinish:
 137         std::vector<RRTNode *> cusp;
 138         while (c) {
 139                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 140                 c = c->bcparent();
 141         }
 142         std::reverse(cusp.begin(), cusp.end());
 143         this->cusp().push_back(cusp);
 144         std::swap(q, empty);
 145 }
 146
 147 void ParallelSlot::fipr(RRTNode *n)
 148 {
 149         return this->fipr(new BicycleCar(n->x(), n->y(), n->h()));
 150 }
 151
 152 void ParallelSlot::fipr(BicycleCar *B)
 153 {
 154         std::vector<RRTNode *> cusp;
 155         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
 156         int di = 1;
 157         if (this->slotSide() == LEFT)
 158                 di = -1;
 159         if (this->slotType() == PERPENDICULAR) {
 160                 this->DH(di * 0.01 / B->out_radi()); // TODO car in slot h()
 161                 RRTNode *cc;
 162                 if (this->slotSide() == LEFT)
 163                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 164                 else
 165                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 166                 BicycleCar *p;
 167                 int i = 1;
 168                 p = B->move(cc, i * this->DH());
 169                 while (
 170                         !this->slot().collide(p->frame())
 171                         && this->slot().collide(p)
 172                 ) {
 173                         delete p;
 174                         i += 10;
 175                         p = B->move(cc, i * this->DH());
 176                 }
 177                 i -= 10;
 178                 p = B->move(cc, i * this->DH());
 179                 while (
 180                         !this->slot().collide(p->frame())
 181                         && this->slot().collide(p)
 182                 ) {
 183                         delete p;
 184                         i += 1;
 185                         p = B->move(cc, i * this->DH());
 186                 }
 187                 i -= 1;
 188                 p = B->move(cc, i * this->DH());
 189                 cusp.push_back(new RRTNode(p->x(), p->y(), p->h()));
 190                 std::reverse(cusp.begin(), cusp.end());
 191                 this->cusp().push_back(cusp);
 192                 return;
 193         }
 194         this->DH(di * 0.01 / B->out_radi());
 195         BicycleCar *c;
 196         c = this->flncr(B);
 197         c->s(B->s() + 1);
 198         while ((
 199                 this->slotSide() == LEFT
 200                 && this->slot().collide(new RRTNode(c->lfx(), c->lfy(), 0))
 201         ) || (
 202                 this->slotSide() == RIGHT
 203                 && this->slot().collide(new RRTNode(c->rfx(), c->rfy(), 0))
 204         )) {
 205                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 206                 BicycleCar *cc = this->flncr(c);
 207                 cc->s(c->s() + 1);
 208                 delete c;
 209                 c = cc;
 210         }
 211         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 212         std::reverse(cusp.begin(), cusp.end());
 213         this->cusp().push_back(cusp);
 214 }
 215
 216 BicycleCar *ParallelSlot::flnc(BicycleCar *B)
 217 {
 218         RRTNode *cc;
 219         if (this->slotSide() == LEFT) {
 220                 if (int(B->s()) % 2 == 0)
 221                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 222                 else
 223                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 224         } else {
 225                 if (int(B->s()) % 2 == 0)
 226                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 227                 else
 228                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 229         }
 230         BicycleCar *p;
 231         int i = 1;
 232         p = B->move(cc, i * this->DH());
 233         while (
 234                 !this->slot().collide(p->frame())
 235                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 236         ) {
 237                 delete p;
 238                 i += 10;
 239                 p = B->move(cc, i * this->DH());
 240         }
 241         i -= 10;
 242         p = B->move(cc, i * this->DH());
 243         while (
 244                 !this->slot().collide(p->frame())
 245                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 246         ) {
 247                 if (this->isInside(p)) {
 248                         i += 1;
 249                         break;
 250                 }
 251                 delete p;
 252                 i += 1;
 253                 p = B->move(cc, i * this->DH());
 254         }
 255         delete p;
 256         return B->move(cc, (i - 1) * this->DH());
 257 }
 258
 259 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
 260 {
 261         RRTNode *cc;
 262         if (this->slotSide() == LEFT) {
 263                 if (int(B->s()) % 2 == 0)
 264                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 265                 else
 266                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 267         } else {
 268                 if (int(B->s()) % 2 == 0)
 269                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 270                 else
 271                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 272         }
 273         BicycleCar *p;
 274         int i = 1;
 275         p = B->move(cc, i * this->DH());
 276         while (
 277                 !this->slot().collide(p->frame())
 278                 && ((
 279                         this->slotSide() == LEFT
 280                         && this->slot().collide(new RRTNode(
 281                                 p->lfx(),
 282                                 p->lfy(),
 283                                 0
 284                         ))
 285                 ) || (
 286                         this->slotSide() == RIGHT
 287                         && this->slot().collide(new RRTNode(
 288                                 p->rfx(),
 289                                 p->rfy(),
 290                                 0
 291                         ))
 292                 ))
 293         ) {
 294                 delete p;
 295                 i += 10;
 296                 p = B->move(cc, i * this->DH());
 297         }
 298         i -= 10;
 299         p = B->move(cc, i * this->DH());
 300         while (!this->slot().collide(p->frame())) {
 301                 if(
 302                         this->slotSide() == LEFT
 303                         && !this->slot().collide(new RRTNode(
 304                                 p->lfx(),
 305                                 p->lfy(),
 306                                 0
 307                         ))
 308                 ) {
 309                         i += 1;
 310                         break;
 311                 }
 312                 if(
 313                         this->slotSide() == RIGHT
 314                         && !this->slot().collide(new RRTNode(
 315                                 p->rfx(),
 316                                 p->rfy(),
 317                                 0
 318                         ))
 319                 ) {
 320                         i += 1;
 321                         break;
 322                 }
 323                 i += 1;
 324                 p = B->move(cc, i * this->DH());
 325         }
 326         delete p;
 327         return B->move(cc, (i - 1) * this->DH());
 328 }
 329
 330 RRTNode *ParallelSlot::fposecenter()
 331 {
 332         return this->slot().bnodes().front();
 333 }
 334
 335 bool ParallelSlot::flast(
 336         RRTNode *P,
 337         bool right,
 338         int il,
 339         std::vector<RRTNode *> &cusp
 340 )
 341 {
 342         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
 343         RRTNode *cc;
 344         if (right)
 345                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 346         else
 347                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 348         BicycleCar *p;
 349         int i = 1;
 350         p = B->move(cc, i * this->DH());
 351         while (!this->slot().collide(p->frame())
 352                         && (
 353                                 (this->DH() > 0 && p->x() <= 0)
 354                                 || (this->DH() < 0 && p->x() >= 0)
 355                         )) {
 356                 delete p;
 357                 i += 10;
 358                 p = B->move(cc, i * this->DH());
 359         }
 360         i -= 10;
 361         p = B->move(cc, i * this->DH());
 362         while (!this->slot().collide(p->frame())
 363                         && (
 364                                 (this->DH() > 0 && p->x() <= 0)
 365                                 || (this->DH() < 0 && p->x() >= 0)
 366                         )) {
 367                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 368                         i += 1;
 369                         break;
 370                 }
 371                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 372                         i += 1;
 373                         break;
 374                 }
 375                 delete p;
 376                 i += 1;
 377                 p = B->move(cc, i * this->DH());
 378         }
 379         delete p;
 380         p = B->move(cc, (i - 1) * this->DH());
 381         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 382                 cusp.push_back(p);
 383                 return true;
 384         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 385                 cusp.push_back(p);
 386                 return true;
 387         } else if (il < 8) {
 388                 cusp.push_back(p);
 389                 return this->flast(p, !right, il + 1, cusp);
 390         }
 391         return false;
 392 }
 393
 394 void ParallelSlot::fpose()
 395 {
 396         bool left = false; // right parking slot
 397         float di = -1;
 398         BicycleCar *CC = new BicycleCar(
 399                 this->fposecenter()->x(),
 400                 this->fposecenter()->y() - 0.01,
 401                 this->slotHeading()
 402         );
 403         BicycleCar *B = new BicycleCar(
 404                 CC->x() - CC->width() / 2,
 405                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 406                 this->slotHeading()
 407         );
 408         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 409                 left = true;
 410                 di = 1;
 411                 delete B;
 412                 B = new BicycleCar(
 413                         CC->x() + CC->width() / 2,
 414                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 415                         this->slotHeading()
 416                 );
 417         }
 418         this->DH(di * 0.01 / CC->out_radi());
 419         BicycleCar *p;
 420         int i = 0;
 421         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 422         while (!this->slot().collide(p->frame())) {
 423                 std::vector<RRTNode *> tmpcusp;
 424                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
 425                 if (this->flast(p, left, 0, tmpcusp)) {
 426                         this->cusp().push_back(tmpcusp);
 427                         return;
 428                 }
 429                 i += 1;
 430                 delete p;
 431                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 432         }
 433 }
 434
 435 BicycleCar *ParallelSlot::getEP()
 436 {
 437         // new pose for parallel parking to right slot
 438         float tnx;
 439         float tny;
 440         float nx;
 441         float ny;
 442         BicycleCar *CC = this->getEPC();
 443         // move left by car width / 2
 444         tnx = CC->x() + CC->width() / 2 * cos(CC->h() + M_PI / 2);
 445         tny = CC->y() + CC->width() / 2 * sin(CC->h() + M_PI / 2);
 446         if (this->slotSide() == LEFT) {
 447                 // move right by car width / 2
 448                 tnx = CC->x() + CC->width() / 2 * cos(CC->h() - M_PI / 2);
 449                 tny = CC->y() + CC->width() / 2 * sin(CC->h() - M_PI / 2);
 450         }
 451         if (this->slotType() == PARALLEL) {
 452                 // move down
 453                 nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 454                 ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 455         } else {
 456                 // move down
 457                 nx = tnx + (CC->length() - CC->wheelbase()) / 2 * cos(CC->h());
 458                 ny = tny + (CC->length() - CC->wheelbase()) / 2 * sin(CC->h());
 459         }
 460         return new BicycleCar(nx, ny, CC->h());
 461 }
 462
 463 BicycleCar *ParallelSlot::getEPC()
 464 {
 465         // new pose for parallel parking to right slot
 466         float ta;
 467         float nx;
 468         float ny;
 469         ta = this->slotHeading() + M_PI;
 470         if (this->slotSide() == RIGHT)
 471                 ta -= M_PI / 4;
 472         else
 473                 ta += M_PI / 4;
 474         nx = this->fposecenter()->x() + 0.01 * cos(ta);
 475         ny = this->fposecenter()->y() + 0.01 * sin(ta);
 476         return new BicycleCar(nx, ny, this->slotHeading());
 477 }
 478
 479 BicycleCar *ParallelSlot::getFP()
 480 {
 481         float x = this->slot().bnodes()[3]->x();
 482         float y = this->slot().bnodes()[3]->y();
 483         float h = this->slotHeading();
 484         float nx;
 485         float ny;
 486         if (this->slotType() == PARALLEL) {
 487                 if (this->slotSide() == LEFT) {
 488                         nx = x + BCAR_WIDTH / 2 * cos(h + M_PI / 2);
 489                         ny = y + BCAR_WIDTH / 2 * sin(h + M_PI / 2);
 490                 } else {
 491                         nx = x + BCAR_WIDTH / 2 * cos(h - M_PI / 2);
 492                         ny = y + BCAR_WIDTH / 2 * sin(h - M_PI / 2);
 493                 }
 494                 x = nx + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * cos(h);
 495                 y = ny + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * sin(h);
 496         } else {
 497                 if (this->slotSide() == LEFT) {
 498                         h -= M_PI / 2;
 499                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 500                                 * cos(h + M_PI);
 501                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 502                                 * sin(h + M_PI);
 503                         x = nx + (BCAR_DIAG_RRADI) * cos(h + M_PI / 2);
 504                         y = ny + (BCAR_DIAG_RRADI) * sin(h + M_PI / 2);
 505                 } else {
 506                         h += M_PI / 2;
 507                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 508                                 * cos(h - M_PI);
 509                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 510                                 * sin(h - M_PI);
 511                         x = nx + (BCAR_DIAG_RRADI) * cos(h - M_PI / 2);
 512                         y = ny + (BCAR_DIAG_RRADI) * sin(h - M_PI / 2);
 513                 }
 514         }
 515         return new BicycleCar(x, y, h);
 516 }
 517
 518 bool ParallelSlot::isInside(BicycleCar *c)
 519 {
 520         bool inside = true;
 521         RRTNode *tmpn;
 522         tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
 523         if (!this->slot().collide(tmpn))
 524                 inside = false;
 525         delete tmpn;
 526         tmpn = new RRTNode(c->lrx(), c->lry(), 0);
 527         if (!this->slot().collide(tmpn))
 528                 inside = false;
 529         delete tmpn;
 530         tmpn = new RRTNode(c->rrx(), c->rry(), 0);
 531         if (!this->slot().collide(tmpn))
 532                 inside = false;
 533         delete tmpn;
 534         tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
 535         if (!this->slot().collide(tmpn))
 536                 inside = false;
 537         delete tmpn;
 538         return inside;
 539 }
 540
 541 struct SamplingInfo ParallelSlot::getSamplingInfo()
 542 {
 543         struct SamplingInfo si;
 544 #ifdef USE_SLOTPLANNER
 545         BicycleCar *CC = this->getEPC();
 546         si.x = this->slot().bnodes()[0]->x();
 547         si.y = this->slot().bnodes()[0]->y();
 548         if (this->slotSide() == RIGHT) {
 549                 si.dx = 1;
 550                 si.dy = 1;
 551                 si.dh = 1;
 552         } else {
 553                 si.dx = -1;
 554                 si.dy = -1;
 555                 si.dh = -1;
 556         }
 557         si.sh = this->slotHeading();
 558         if (this->slotType() == PARALLEL) {
 559                 si.h = this->slotHeading() - acos(EDIST(
 560                         this->slot().bnodes()[0],
 561                         this->slot().bnodes()[1]
 562                 ) / BCAR_LENGTH);
 563         } else {
 564                 si.h = M_PI / 2 / 3;
 565         }
 566 #else
 567         si.x = this->slot().bnodes()[3]->x() - this->slot().bnodes()[0]->x();
 568         si.x /= 2;
 569         si.x += this->slot().bnodes()[0]->x();
 570         si.y = this->slot().bnodes()[3]->y() - this->slot().bnodes()[0]->y();
 571         si.y /= 2;
 572         si.y += this->slot().bnodes()[0]->y();
 573         if (this->slotSide() == RIGHT) {
 574                 si.dx = 1;
 575                 si.dy = 1;
 576                 si.dh = 1;
 577         } else {
 578                 si.dx = -1;
 579                 si.dy = -1;
 580                 si.dh = -1;
 581         }
 582         si.r = EDIST(this->slot().bnodes()[0], this->slot().bnodes()[3]) / 2;
 583         si.r *= 2;
 584         si.sh = this->slotHeading();
 585         si.h = M_PI / 4;
 586 #endif
 587         return si;
 588 }